1 module pry.combinators; 2 3 import pry.traits; 4 import std.meta; 5 6 private: 7 8 struct RepImpl(bool collect, size_t minTimes, Parser){ 9 alias Stream = ParserStream!Parser; 10 static if(collect) 11 alias Value = ParserValue!Parser[]; 12 else 13 alias Value = Stream.Range; 14 Parser parser; 15 16 bool parse(ref Stream stream, ref Value value, ref Stream.Error err) { 17 auto start = stream.mark; 18 ParserValue!Parser tmp; 19 for(size_t i = 0; i<minTimes; i++) { 20 if(!parser.parse(stream, tmp, err)){ 21 stream.restore(start); 22 return false; 23 } 24 static if(collect) value ~= tmp; 25 } 26 while(parser.parse(stream, tmp, err)){ 27 static if(collect) value ~= tmp; 28 } 29 static if(!collect) 30 value = stream.slice(start); 31 return true; 32 } 33 } 34 35 36 /// Apply parser for minTimes times or more and return consumed range. 37 public auto rep(size_t minTimes=1, Parser)(Parser parser) 38 if(isParser!Parser){ 39 return RepImpl!(false, minTimes, Parser)(parser); 40 } 41 42 /// Apply parser for minTimes times or more and return array of results. 43 public auto array(size_t minTimes=1, Parser)(Parser parser) 44 if(isParser!Parser){ 45 return RepImpl!(true, minTimes, Parser)(parser); 46 } 47 48 unittest 49 { 50 import pry.atoms, pry.stream; 51 alias S = SimpleStream!string; 52 with(parsers!S) 53 { 54 auto p = tk!'a'.rep!2; 55 string r; 56 S.Error err; 57 auto s = S("aaac"); 58 assert(p.parse(s, r, err)); 59 assert(r == "aaa"); 60 61 s = S("a"); 62 assert(!p.parse(s, r, err)); 63 assert(err.location == 1); 64 assert(err.reason == "unexpected end of stream"); 65 66 auto p2 = range!('a', 'b').array; 67 dchar[] r2; 68 s = S("aba"); 69 assert(p2.parse(s, r2, err)); 70 assert(r2 == "aba"d); 71 assert(s.empty); 72 } 73 } 74 75 76 struct Map(Parser, alias f) { 77 alias Stream = ParserStream!Parser; 78 alias Value = typeof(f(ParserValue!Parser.init)); 79 alias mapper = f; 80 Parser parser; 81 82 bool parse(ref Stream stream, ref Value value, ref Stream.Error err){ 83 ParserValue!Parser tmp; 84 if(parser.parse(stream, tmp, err)){ 85 value = f(tmp); 86 return true; 87 } 88 else 89 return false; 90 } 91 } 92 93 /// Apply a mapping function to the value of parser. 94 public template map(alias f) 95 { 96 auto map(Parser)(Parser parser) 97 if(isParser!Parser){ 98 return Map!(Parser, f)(parser); 99 } 100 } 101 102 /// 103 unittest { 104 import std.conv; 105 import pry.atoms, pry.stream; 106 alias S = SimpleStream!string; 107 with(parsers!S) { 108 auto digits = range!('0', '9').rep.map!(x=>x.to!int); 109 S s = S("90"); 110 int r; 111 S.Error err; 112 assert(digits.parse(s, r, err)); 113 assert(r == 90); 114 s = S("a"); 115 assert(!digits.parse(s, r, err)); 116 assert(err.location == 0); 117 } 118 } 119 120 121 122 struct Seq(P...){ 123 import std.typecons; 124 alias Stream = ParserStream!(P[0]); 125 alias Values = staticMap!(ParserValue, P); 126 P parsers; 127 128 bool parse(ref Stream stream, ref Tuple!Values value, ref Stream.Error err) { 129 auto save = stream.mark; 130 foreach(i, ref p; parsers) { 131 if(!p.parse(stream, value[i], err)){ 132 stream.restore(save); 133 return false; 134 } 135 } 136 return true; 137 } 138 } 139 140 /// Apply multiple parsers one after another as a sequence. 141 public auto seq(P...)(P parsers) 142 if(allSatisfy!(isParser, P)){ 143 static if(P.length == 0) 144 return Nothing(); 145 else 146 return Seq!P(parsers); 147 } 148 149 /// 150 unittest { 151 import pry.atoms, pry.stream; 152 import std.range.primitives, std.typecons; 153 alias S = SimpleStream!string; 154 with(parsers!S) { 155 auto elements = seq(tk!'a', range!('a', 'd'), tk!'c'); 156 S s = S("abc"); 157 Tuple!(dchar, dchar, dchar) val; 158 S.Error err; 159 assert(elements.parse(s, val, err)); 160 assert(s.empty); 161 assert(val == tuple('a', 'b', 'c')); 162 s = S("axc"); 163 assert(!elements.parse(s, val, err)); 164 assert(s.front == 'a'); 165 assert(err.location == 1); 166 } 167 } 168 169 struct Nothing{} 170 171 struct TList(T...){} 172 173 template commonPrefixLength(T1, T2){ 174 static if(is(T1 == TList!U1, U1...)){ 175 static if(is(T2 == TList!U2, U2...)){ 176 static if(U1.length == 0 || U2.length == 0){ 177 enum commonPrefixLength = 0; 178 } 179 else static if(is(U1[0] == U2[0])){ 180 enum commonPrefixLength = 1 + 181 commonPrefixLength!(TList!(U1[1..$]), TList!(U2[1..$])); 182 } 183 else { 184 enum commonPrefixLength = 0; 185 } 186 } 187 } 188 } 189 190 auto commonPrefix(P1, P2)(P1 p1, P2 p2){ 191 static if(is(P1 : Seq!U1, U1...)){ 192 enum isSeq = true; 193 alias T1 = TList!U1; 194 } 195 else{ 196 enum isSeq = false; 197 alias T1 = TList!P1; 198 } 199 static if(is(P2 : Seq!U2, U2...)){ 200 alias T2 = TList!U2; 201 } 202 else{ 203 alias T2 = TList!P2; 204 } 205 enum len = commonPrefixLength!(T1,T2); 206 static if(isSeq) 207 return seq(p1.parsers[0..len]); 208 else static if(len) 209 return seq(p1); 210 else 211 return Nothing(); 212 } 213 214 auto commonPrefix(P...)(P p) 215 if(P.length > 2){ 216 return commonPrefix(commonPrefix(p[0], p[1]), p[2..$]); 217 } 218 219 unittest { 220 import pry.atoms, pry.stream; 221 alias S = SimpleStream!string; 222 with(parsers!S){ 223 auto p1 = seq(tk!'a', tk!'b'); 224 auto p2 = seq(tk!'a'); 225 auto p3 = tk!'a'; 226 auto p4 = seq(tk!'b', tk!'a'); 227 assert(commonPrefix(p1, p2) == seq(tk!'a')); 228 assert(commonPrefix(p2, p3) == seq(tk!'a')); 229 assert(commonPrefix(p3, p3) == seq(tk!'a')); 230 assert(commonPrefix(p3, p1) == seq(tk!'a')); 231 assert(commonPrefix(p1, p4) == Nothing()); 232 assert(commonPrefix(p3, p4) == Nothing()); 233 assert(commonPrefix(p4, p3) == Nothing()); 234 assert(commonPrefix(p1, p2, p3) == seq(tk!'a')); 235 assert(commonPrefix(p1, p2, p3, p4) == Nothing()); 236 } 237 } 238 239 auto suffix(P1, P2)(P1 prefix, P2 parser) 240 if(isParser!P1 && isParser!P2){ 241 static if(is(P1 : Seq!U1, U1...)){ 242 alias T1 = TList!U1; 243 } 244 else{ 245 alias T1 = TList!P1; 246 } 247 static if(is(P2 : Seq!U2, U2...)){ 248 enum isSeq = true; 249 alias T2 = TList!U2; 250 } 251 else{ 252 enum isSeq = false; 253 alias T2 = TList!P2; 254 } 255 enum len = commonPrefixLength!(T1,T2); 256 static if(is(T1 : TList!U, U...)){ 257 static assert(len == U.length); 258 } 259 static if(isSeq){ 260 return seq(parser.parsers[len..$]); 261 } 262 else{ 263 static if(len > 0) 264 return Nothing(); 265 else 266 return seq(parser); 267 } 268 } 269 270 unittest{ 271 import pry.atoms, pry.stream; 272 alias S = SimpleStream!string; 273 with(parsers!S){ 274 auto p1 = seq(tk!'a', tk!'b'); 275 auto p2 = seq(tk!'a'); 276 auto p3 = tk!'a'; 277 auto p4 = seq(tk!'b', tk!'a'); 278 assert(suffix(p2, p1) == seq(tk!'b')); 279 assert(suffix(p3, p1) == seq(tk!'b')); 280 assert(suffix(p2, p3) == Nothing()); 281 } 282 } 283 284 template Unmap(P){ 285 static if(is(P : Map!(U, f), alias f, U)){ 286 alias Unmap = U; 287 } 288 else { 289 alias Unmap = P; 290 } 291 } 292 293 auto unmap(P)(P parser){ 294 static if(is(P : Map!(U, f), alias f, U)){ 295 return parser.parser; 296 } 297 else { 298 return parser; 299 } 300 } 301 302 unittest{ 303 import pry.atoms, pry.stream; 304 alias S = SimpleStream!string; 305 with(parsers!S){ 306 auto x = tk!'a'.map!(x => 1); 307 assert(unmap(x) == tk!'a'); 308 assert(unmap(unmap(x)) == tk!'a'); 309 } 310 } 311 312 struct Any(P...){ 313 import std.variant, std.typecons; 314 alias Stream = ParserStream!(P[0]); 315 alias Values = NoDuplicates!(staticMap!(ParserValue, P)); 316 317 static if(Values.length == 1) 318 alias Value = Values[0]; 319 else 320 alias Value = Algebraic!Values; 321 322 P parsers; 323 alias Prefix = typeof(extractPrefix()); 324 Prefix prefix; 325 326 template mapper(size_t i){ 327 static if(is(P[i] == Map!(U, f), U, alias f)) 328 alias mapper = P[i].mapper; 329 else 330 alias mapper = x => x; 331 } 332 333 this(P parsers){ 334 this.parsers = parsers; 335 prefix = extractPrefix(); 336 } 337 338 auto extractPrefix(){ 339 staticMap!(Unmap, P) unmapped = void; 340 foreach(i, ref p; parsers){ 341 unmapped[i] = unmap(p); 342 } 343 return commonPrefix(unmapped); 344 } 345 346 auto combine(T1, T2)(T1 prefixValue, T2 suffixValue){ 347 static if(is(T1 == Nothing)){ 348 return suffixValue; 349 } 350 else{ 351 return tuple(prefixValue.expand, suffixValue.expand); 352 } 353 } 354 355 bool parse(ref Stream stream, ref Value value, ref Stream.Error err) { 356 static if(is(Prefix == Nothing)){ 357 Nothing prefixValue; 358 } 359 else{ 360 ParserValue!Prefix prefixValue; 361 if(!prefix.parse(stream, prefixValue, err)){ 362 return false; 363 } 364 } 365 Stream.Error current, deepest; 366 bool ret = false; 367 foreach(i, ref p; parsers) { 368 static if(is(Prefix == Nothing)) 369 auto sp = unmap(p); 370 else 371 auto sp = suffix(prefix, unmap(p)); 372 alias Suffix = typeof(sp); 373 static if(is(Suffix == Nothing)){ 374 value = mapper!i(prefixValue.expand); 375 ret = true; 376 goto L_end; 377 } 378 else { 379 ParserValue!Suffix suffixValue; 380 static if(i == 0){ 381 if(sp.parse(stream, suffixValue, deepest)){ 382 value = mapper!i(combine(prefixValue, suffixValue)); 383 return true; 384 } 385 } 386 else { 387 if(sp.parse(stream, suffixValue, current)){ 388 value = mapper!i(combine(prefixValue, suffixValue)); 389 return true; 390 } 391 // pick the deeper error 392 if(deepest.location < current.location){ 393 deepest = current; 394 } 395 } 396 } 397 } 398 L_end: 399 err = deepest; 400 return ret; 401 } 402 } 403 404 /// Try each of provided parsers until one succeeds. 405 public auto any(P...)(P parsers) 406 if(allSatisfy!(isParser, P)){ 407 return Any!P(parsers); 408 } 409 410 /// 411 unittest { 412 import pry.atoms, pry.stream; 413 import std.range.primitives, std.conv, std.variant; 414 alias S = SimpleStream!string; 415 with(parsers!S) { 416 auto digits = range!('0', '9').rep.map!(x => x.to!int); 417 static assert(isParser!(typeof(digits))); 418 auto parser = any(tk!'a', digits); 419 S s = "10a"; 420 S.Error err; 421 Algebraic!(dchar, int) value; 422 assert(parser.parse(s, value, err)); 423 assert(value == 10); 424 assert(parser.parse(s, value, err)); 425 assert(value == cast(dchar)'a'); 426 assert(s.empty); 427 } 428 } 429 430 unittest { 431 import pry.atoms, pry.stream; 432 alias S = SimpleStream!string; 433 with(parsers!S) { 434 auto e = dynamic!int; 435 e = any( 436 seq(tk!'0', e).map!(x => 1), 437 tk!'1'.map!(x => 0) 438 ); 439 S.Error err; 440 int val; 441 S s = S("0001"); 442 assert(e.parse(s, val, err)); 443 } 444 } 445 446 unittest { 447 import pry.atoms, pry.stream; 448 import std.typecons; 449 alias S = SimpleStream!string; 450 with(parsers!S) { 451 auto p = any( 452 seq(tk!'0', tk!'0'), 453 seq(tk!'1', tk!'1') 454 ); 455 S s = "01".stream; 456 Tuple!(dchar, dchar) value; 457 S.Error err; 458 assert(!p.parse(s, value, err)); 459 assert(err.location == 1); 460 } 461 }