1 module nxt.find_ex; 2 3 import std.typecons: Tuple, tuple; 4 import std..string: CaseSensitive; 5 import std.functional: binaryFun; 6 7 enum FindContext { inWord, inSymbol, 8 asWord, asSymbol } 9 10 /** Return true if $(D a) is a C-style Identifier symbol character. */ 11 bool isSymbol(T)(in T a) 12 @safe pure nothrow @nogc 13 { 14 import std.ascii: isAlpha; 15 return a.isAlpha || a == '_'; 16 } 17 18 bool isSymbolASCII(string rest, ptrdiff_t off, size_t end) 19 @safe pure nothrow @nogc 20 in 21 { 22 assert(end <= rest.length); 23 } 24 do 25 { 26 import std.ascii: isAlphaNum; 27 return ((off == 0 || // either beginning of line 28 !rest[off - 1].isAlphaNum && 29 rest[off - 1] != '_') && 30 (end == rest.length || // either end of line 31 !rest[end].isAlphaNum && 32 rest[end] != '_')); 33 } 34 35 /// 36 @safe pure nothrow @nogc unittest 37 { 38 assert(isSymbolASCII("alpha", 0, 5)); 39 assert(isSymbolASCII(" alpha ", 1, 6)); 40 assert(!isSymbolASCII("driver", 0, 5)); 41 assert(!isSymbolASCII("a_word", 0, 1)); 42 assert(!isSymbolASCII("first_a_word", 6, 7)); 43 } 44 45 bool isWordASCII(string rest, ptrdiff_t off, size_t end) 46 @safe pure nothrow @nogc 47 in 48 { 49 assert(end <= rest.length); 50 } 51 do 52 { 53 import std.ascii: isAlphaNum; 54 return ((off == 0 || // either beginning of line 55 !rest[off - 1].isAlphaNum) && 56 (end == rest.length || // either end of line 57 !rest[end].isAlphaNum)); 58 } 59 60 /// 61 @safe pure nothrow @nogc unittest 62 { 63 assert(isSymbolASCII("alpha", 0, 5)); 64 assert(isSymbolASCII(" alpha ", 1, 6)); 65 assert(!isSymbolASCII("driver", 0, 5)); 66 assert(isWordASCII("a_word", 0, 1)); 67 assert(isWordASCII("first_a_word", 6, 7)); 68 assert(isWordASCII("first_a", 6, 7)); 69 } 70 71 // Parameterize on isAlpha and isSymbol. 72 73 /** Find $(D needle) as Word or Symbol Acronym at $(D haystackOffset) in $(D haystack). 74 TODO Make it compatible (specialized) for InputRange or BidirectionalRange. 75 */ 76 Tuple!(R, ptrdiff_t[]) findAcronymAt(alias pred = "a == b", 77 R, 78 E)(R haystack, 79 E needle, 80 FindContext ctx = FindContext.inWord, 81 CaseSensitive cs = CaseSensitive.yes, // TODO Use this 82 size_t haystackOffset = 0) @safe pure 83 { 84 import std.ascii: isAlpha; 85 import std.algorithm: find; 86 import std.range: empty; 87 88 scope auto aOffs = new ptrdiff_t[needle.length]; // acronym hit offsets 89 90 auto rest = haystack[haystackOffset..$]; 91 while (needle.length <= rest.length) // for each new try at finding the needle at remainding part of haystack 92 { 93 /* debug dbg(needle, ", ", rest); */ 94 95 // find first character 96 size_t nIx = 0; // needle index 97 rest = rest.find!pred(needle[nIx]); // reuse std.algorithm: find! 98 if (rest.empty) { return tuple(rest, ptrdiff_t[].init); } // degenerate case 99 aOffs[nIx++] = &rest[0] - &haystack[0]; // store hit offset and advance acronym 100 rest = rest[1 .. $]; 101 const ix0 = aOffs[0]; 102 103 // check context before point 104 final switch (ctx) 105 { 106 case FindContext.inWord: break; // TODO find word characters before point and set start offset 107 case FindContext.inSymbol: break; // TODO find symbol characters before point and set start offset 108 case FindContext.asWord: 109 if (ix0 >= 1 && haystack[ix0-1].isAlpha) { goto miss; } // quit if not word start 110 break; 111 case FindContext.asSymbol: 112 if (ix0 >= 1 && haystack[ix0-1].isSymbol) { goto miss; } // quit if not symbol stat 113 break; 114 } 115 116 while (rest) // while elements left in haystack 117 { 118 119 // Check elements in between 120 ptrdiff_t hit = -1; 121 import std.algorithm: countUntil; 122 final switch (ctx) 123 { 124 case FindContext.inWord: 125 case FindContext.asWord: 126 hit = rest.countUntil!(x => (binaryFun!pred(x, needle[nIx])) || !x.isAlpha); break; 127 case FindContext.inSymbol: 128 case FindContext.asSymbol: 129 hit = rest.countUntil!(x => (binaryFun!pred(x, needle[nIx])) || !x.isSymbol); break; 130 } 131 if (hit == -1) { goto miss; } // no hit this time 132 133 // Check if hit 134 if (hit == rest.length || // if we searched till the end 135 rest[hit] != needle[nIx]) // acronym letter not found 136 { 137 rest = haystack[aOffs[0]+1 .. $]; // try beyond hit 138 goto miss; // no hit this time 139 } 140 141 aOffs[nIx++] = (&rest[0] - &haystack[0]) + hit; // store hit offset and advance acronym 142 if (nIx == needle.length) // if complete acronym found 143 { 144 return tuple(haystack[aOffs[0] .. aOffs[$-1] + 1], aOffs) ; // return its length 145 } 146 rest = rest[hit+1 .. $]; // advance in source beyound hit 147 } 148 miss: 149 continue; 150 } 151 return tuple(R.init, ptrdiff_t[].init); // no hit 152 } 153 154 /// 155 @safe pure unittest 156 { 157 assert("size_t".findAcronymAt("sz_t", FindContext.inWord)[0] == "size_t"); 158 assert("size_t".findAcronymAt("sz_t", FindContext.inSymbol)[0] == "size_t"); 159 assert("åäö_ab".findAcronymAt("ab")[0] == "ab"); 160 assert("fopen".findAcronymAt("fpn")[0] == "fopen"); 161 assert("fopen_".findAcronymAt("fpn")[0] == "fopen"); 162 assert("_fopen".findAcronymAt("fpn", FindContext.inWord)[0] == "fopen"); 163 assert("_fopen".findAcronymAt("fpn", FindContext.inSymbol)[0] == "fopen"); 164 assert("f_open".findAcronymAt("fpn", FindContext.inWord)[0] == []); 165 assert("f_open".findAcronymAt("fpn", FindContext.inSymbol)[0] == "f_open"); 166 }