1 /**
2 
3 Various @nogc alternatives. This file includes parts of `std.process`, `std.random`, `std.uuid`.
4 
5 Authors:
6   $(HTTP guillaumepiolat.fr, Guillaume Piolat)
7   $(LINK2 https://github.com/kyllingstad, Lars Tandle Kyllingstad),
8   $(LINK2 https://github.com/schveiguy, Steven Schveighoffer),
9   $(HTTP thecybershadow.net, Vladimir Panteleev)
10 
11 Copyright:
12  Copyright (c) 2016, Guillaume Piolat.
13  Copyright (c) 2013, Lars Tandle Kyllingstad (std.process).
14  Copyright (c) 2013, Steven Schveighoffer (std.process).
15  Copyright (c) 2013, Vladimir Panteleev (std.process).
16 
17  License:
18    $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
19 */
20 module dplug.core.nogc;
21 
22 import core.stdc..string: strdup, memcpy, strlen;
23 import core.stdc.stdlib: malloc, free, getenv;
24 import core.memory: GC;
25 import core.exception: onOutOfMemoryErrorNoGC;
26 
27 import std.conv: emplace;
28 import std.traits;
29 import std.array: empty;
30 import std.exception: assumeUnique;
31 
32 // This module provides many utilities to deal with @nogc nothrow, in a situation with the runtime disabled.
33 
34 //
35 // Faking @nogc
36 //
37 
38 auto assumeNoGC(T) (T t)
39 {
40     static if (isFunctionPointer!T || isDelegate!T)
41     {
42         enum attrs = functionAttributes!T | FunctionAttribute.nogc;
43         return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs)) t;
44     }
45     else
46         static assert(false);
47 }
48 
49 auto assumeNothrowNoGC(T) (T t)
50 {
51     static if (isFunctionPointer!T || isDelegate!T)
52     {
53         enum attrs = functionAttributes!T | FunctionAttribute.nogc | FunctionAttribute.nothrow_;
54         return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs)) t;
55     }
56     else
57         static assert(false);
58 }
59 
60 unittest
61 {
62     void funcThatDoesGC()
63     {
64         int a = 4;
65         int[] b = [a, a, a];
66     }
67 
68     void anotherFunction() nothrow @nogc
69     {
70         assumeNothrowNoGC( (){ funcThatDoesGC(); } )();
71     }
72 
73     void aThirdFunction() @nogc
74     {
75         assumeNoGC( () { funcThatDoesGC(); } )();
76     }
77 }
78 
79 
80 //
81 // Optimistic .destroy, which is @nogc nothrow by breaking the type-system
82 //
83 
84 // for classes
85 void destroyNoGC(T)(T x) nothrow @nogc if (is(T == class) || is(T == interface))
86 {
87     assumeNothrowNoGC(
88         (T x)
89         {
90             return destroy(x);
91         })(x);
92 }
93 
94 // for struct
95 void destroyNoGC(T)(ref T obj) nothrow @nogc if (is(T == struct))
96 {
97     assumeNothrowNoGC(
98         (ref T x)
99         {
100             return destroy(x);
101         })(obj);
102 }
103 /*
104 void destroyNoGC(T : U[n], U, size_t n)(ref T obj) nothrow @nogc
105 {
106     assumeNothrowNoGC(
107         (T x)
108         {
109             return destroy(x);
110         })(obj);
111 }*/
112 
113 void destroyNoGC(T)(ref T obj) nothrow @nogc
114     if (!is(T == struct) && !is(T == class) && !is(T == interface))
115 {
116     assumeNothrowNoGC(
117                       (ref T x)
118                       {
119                           return destroy(x);
120                       })(obj);
121 }
122 
123 
124 
125 //
126 // Constructing and destroying without the GC.
127 //
128 
129 /// Allocates and construct a struct or class object.
130 /// Returns: Newly allocated object.
131 auto mallocNew(T, Args...)(Args args)
132 {
133     static if (is(T == class))
134         immutable size_t allocSize = __traits(classInstanceSize, T);
135     else
136         immutable size_t allocSize = T.sizeof;
137 
138     void* rawMemory = malloc(allocSize);
139     if (!rawMemory)
140         onOutOfMemoryErrorNoGC();
141 
142     static if (is(T == class))
143     {
144         T obj = emplace!T(rawMemory[0 .. allocSize], args);
145     }
146     else
147     {
148         T* obj = cast(T*)rawMemory;
149         emplace!T(obj, args);
150     }
151 
152     return obj;
153 }
154 
155 /// Destroys and frees a class object created with $(D mallocEmplace).
156 void destroyFree(T)(T p) if (is(T == class))
157 {
158     if (p !is null)
159     {
160         destroyNoGC(p);
161         free(cast(void*)p);
162     }
163 }
164 
165 /// Destroys and frees an interface object created with $(D mallocEmplace).
166 void destroyFree(T)(T p) if (is(T == interface))
167 {
168     if (p !is null)
169     {
170         void* here = cast(void*)(cast(Object)p);
171         destroyNoGC(p);
172         free(cast(void*)here);
173     }
174 }
175 
176 /// Destroys and frees a non-class object created with $(D mallocEmplace).
177 void destroyFree(T)(T* p) if (!is(T == class))
178 {
179     if (p !is null)
180     {
181         destroyNoGC(p);
182         free(cast(void*)p);
183     }
184 }
185 
186 
187 unittest
188 {
189     class A
190     {
191         int _i;
192         this(int i)
193         {
194             _i = i;
195         }
196     }
197 
198     struct B
199     {
200         int i;
201     }
202 
203     void testMallocEmplace()
204     {
205         A a = mallocNew!A(4);
206         destroyFree(a);
207 
208         B* b = mallocNew!B(5);
209         destroyFree(b);
210     }
211 
212     testMallocEmplace();
213 }
214 
215 version( D_InlineAsm_X86 )
216 {
217     version = AsmX86;
218 }
219 else version( D_InlineAsm_X86_64 )
220 {
221     version = AsmX86;
222 }
223 
224 /// Allocates a slice with `malloc`.
225 T[] mallocSlice(T)(size_t count) nothrow @nogc
226 {
227     T[] slice = mallocSliceNoInit!T(count);
228     static if (is(T == struct))
229     {
230         // we must avoid calling struct destructors with uninitialized memory
231         for(size_t i = 0; i < count; ++i)
232         {
233             T uninitialized;
234             memcpy(&slice[i], &uninitialized, T.sizeof);
235         }
236     }
237     else
238         slice[0..count] = T.init;
239     return slice;
240 }
241 
242 /// Allocates a slice with `malloc`, but does not initialize the content.
243 T[] mallocSliceNoInit(T)(size_t count) nothrow @nogc
244 {
245     T* p = cast(T*) malloc(count * T.sizeof);
246     return p[0..count];
247 }
248 
249 /// Frees a slice allocated with `mallocSlice`.
250 void freeSlice(T)(const(T)[] slice) nothrow @nogc
251 {
252     free(cast(void*)(slice.ptr)); // const cast here
253 }
254 
255 /// Duplicates a slice with `malloc`. Equivalent to `.dup`
256 /// Has to be cleaned-up with `free()`.
257 T[] mallocDup(T)(const(T)[] slice) nothrow @nogc if (!is(T == struct))
258 {
259     T[] copy = mallocSliceNoInit!T(slice.length);
260     memcpy(copy.ptr, slice.ptr, slice.length * T.sizeof);
261     return copy;
262 }
263 
264 /// Duplicates a slice with `malloc`. Equivalent to `.idup`
265 /// Has to be cleaned-up with `free()`.
266 immutable(T)[] mallocIDup(T)(const(T)[] slice) nothrow @nogc if (!is(T == struct))
267 {
268     return assumeUnique(mallocDup!T(slice));
269 }
270 
271 /// Duplicates a zero-terminated string with `malloc`, return a `char[]`. Equivalent to `.dup`
272 /// Has to be cleaned-up with `free()`.
273 /// Note: The zero-terminating byte is preserved. This allow to have a string which also can be converted
274 /// to a C string with `.ptr`. However the zero byte is not included in slice length.
275 char[] stringDup(const(char)* cstr) nothrow @nogc
276 {
277     assert(cstr !is null);
278     size_t len = strlen(cstr);
279     char* copy = strdup(cstr);
280     return copy[0..len];
281 }
282 
283 /// Duplicates a zero-terminated string with `malloc`, return a `string`. Equivalent to `.idup`
284 /// Has to be cleaned-up with `free()`.
285 /// Note: The zero-terminating byte is preserved. This allow to have a string which also can be converted
286 /// to a C string with `.ptr`. However the zero byte is not included in slice length.
287 string stringIDup(const(char)* cstr) nothrow @nogc
288 {
289     return assumeUnique(stringDup(cstr));
290 }
291 
292 unittest
293 {
294     int[] slice = mallocSlice!int(4);
295     freeSlice(slice);
296     assert(slice[3] == int.init);
297 
298     slice = mallocSliceNoInit!int(4);
299     freeSlice(slice);
300 
301     slice = mallocSliceNoInit!int(0);
302     assert(slice == []);
303     freeSlice(slice);
304 }
305 
306 /// Semantic function to check that a D string implicitely conveys a 
307 /// termination byte after the slice.
308 /// (typically those comes from string literals or `stringDup`/`stringIDup`)
309 const(char)* assumeZeroTerminated(const(char)[] input) nothrow @nogc
310 {
311     if (input.ptr is null)
312         return null;
313 
314     // Check that the null character is there
315     assert(input.ptr[input.length] == '\0');
316     return input.ptr;
317 }
318 
319 
320 //
321 // @nogc sorting.
322 //
323 
324 /// Must return -1 if a < b
325 ///              0 if a == b
326 ///              1 if a > b
327 alias nogcComparisonFunction(T) = int delegate(in T a, in T b) nothrow @nogc;
328 
329 //
330 // STABLE IN-PLACE SORT (implementation is at bottom of file)
331 //
332 
333 void grailSort(T)(T[] inoutElements, nogcComparisonFunction!T comparison) nothrow @nogc
334 {
335     GrailSort!T(inoutElements.ptr, cast(int)(inoutElements.length), comparison);
336 }
337 
338 unittest
339 {
340     int[2][] testData = [[110, 0], [5, 0], [10, 0], [3, 0], [110, 1], [5, 1], [10, 1], [3, 1]];
341     grailSort!(int[2])(testData, (a, b) => (a[0] - b[0]));
342     assert(testData == [[3, 0], [3, 1], [5, 0], [5, 1], [10, 0], [10, 1], [110, 0], [110, 1]]);
343 }
344 
345 
346 //
347 // STABLE MERGE SORT
348 //
349 
350 /// Stable merge sort, using a temporary array.
351 /// Array A[] has the items to sort.
352 /// Array B[] is a work array.
353 /// `grailSort` is approx. 30% slower but doesn't need a scratchBuffer.
354 void mergeSort(T)(T[] inoutElements, T[] scratchBuffer, nogcComparisonFunction!T comparison) nothrow @nogc
355 {
356     // Left source half is A[ iBegin:iMiddle-1].
357     // Right source half is A[iMiddle:iEnd-1   ].
358     // Result is            B[ iBegin:iEnd-1   ].
359     void topDownMerge(T)(T* A, int iBegin, int iMiddle, int iEnd, T* B) nothrow @nogc
360     {
361         int i = iBegin;
362         int j = iMiddle;
363 
364         // While there are elements in the left or right runs...
365         for (int k = iBegin; k < iEnd; k++)
366         {
367             // If left run head exists and is <= existing right run head.
368             if ( i < iMiddle && ( j >= iEnd || (comparison(A[i], A[j]) <= 0) ) )
369             {
370                 B[k] = A[i];
371                 i = i + 1;
372             }
373             else
374             {
375                 B[k] = A[j];
376                 j = j + 1;
377             }
378         }
379     }
380 
381     // Sort the given run of array A[] using array B[] as a source.
382     // iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
383     void topDownSplitMerge(T)(T* B, int iBegin, int iEnd, T* A) nothrow @nogc
384     {
385         if(iEnd - iBegin < 2)                       // if run size == 1
386             return;                                 //   consider it sorted
387         // split the run longer than 1 item into halves
388         int iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
389         // recursively sort both runs from array A[] into B[]
390         topDownSplitMerge!T(A, iBegin,  iMiddle, B);  // sort the left  run
391         topDownSplitMerge!T(A, iMiddle,    iEnd, B);  // sort the right run
392         // merge the resulting runs from array B[] into A[]
393         topDownMerge!T(B, iBegin, iMiddle, iEnd, A);
394     }
395 
396     assert(inoutElements.length == scratchBuffer.length);
397     int n = cast(int)inoutElements.length;
398     scratchBuffer[] = inoutElements[]; // copy data into temporary buffer
399     topDownSplitMerge(scratchBuffer.ptr, 0, n, inoutElements.ptr);
400 }
401 
402 unittest
403 {
404     int[2][] scratch;
405     scratch.length = 8;
406     int[2][] testData = [[110, 0], [5, 0], [10, 0], [3, 0], [110, 1], [5, 1], [10, 1], [3, 1]];
407     mergeSort!(int[2])(testData, scratch, (a, b) => (a[0] - b[0]));
408     assert(testData == [[3, 0], [3, 1], [5, 0], [5, 1], [10, 0], [10, 1], [110, 0], [110, 1]]);
409 }
410 
411 /// To call for something that should never happen, but we still
412 /// want to make a "best effort" at runtime even if it can be meaningless.
413 /// MAYDO: change that name, it's not actually unrecoverable
414 /// MAYDO: stop using that function
415 void unrecoverableError() nothrow @nogc
416 {
417     debug
418     {
419         // Crash unconditionally
420         assert(false);
421     }
422     else
423     {
424         // There is a trade-off here, if we crash immediately we will be
425         // correctly identified by the user as the origin of the bug, which
426         // is always helpful.
427         // But crashing may in many-case also crash the host, which is not very friendly.
428         // Eg: a plugin not instancing vs host crashing.
429         // The reasoning is that the former is better from the user POV.
430     }
431 }
432 
433 
434 /// A bit faster than a dynamic cast.
435 /// This is to avoid TypeInfo look-up.
436 T unsafeObjectCast(T)(Object obj)
437 {
438     return cast(T)(cast(void*)(obj));
439 }
440 
441 /// Outputs a debug string in either:
442 ///  - stdout on POSIX-like (visible in the command-line)
443 ///  - the Output Windows on Windows (visible withing Visual Studio or with dbgview.exe)
444 /// Warning: no end-of-line added!
445 void debugLog(const(char)* message) nothrow @nogc
446 {
447     version(Windows)
448     {
449         import core.sys.windows.windows;
450         OutputDebugStringA(message);
451     }
452     else
453     {
454         import core.stdc.stdio;
455         printf("%s", message);
456     }
457 }
458 
459 
460 /// Inserts a breakpoint instruction. useful to trigger the debugger.
461 void debugBreak() nothrow @nogc
462 {
463     version( AsmX86 )
464     {
465         asm nothrow @nogc
466         {
467             int 3;
468         }
469     }
470     else version( GNU )
471     {
472         // __builtin_trap() is not the same thing unfortunately
473         asm
474         {
475             "int $0x03" : : : ;
476         }
477     }
478     else
479     {
480         static assert(false, "No debugBreak() for this compiler");
481     }
482 }
483 
484 
485 // Copy source into dest.
486 // dest must contain room for maxChars characters
487 // A zero-byte character is then appended.
488 void stringNCopy(char* dest, size_t maxChars, const(char)[] source) nothrow @nogc
489 {
490     if (maxChars == 0)
491         return;
492 
493     size_t max = maxChars < source.length ? maxChars - 1 : source.length;
494     for (int i = 0; i < max; ++i)
495         dest[i] = source[i];
496     dest[max] = '\0';
497 }
498 
499 
500 //
501 // Low-cost C string conversions
502 //
503 alias CString = CStringImpl!char;
504 alias CString16 = CStringImpl!wchar;
505 
506 /// Zero-terminated C string, to replace toStringz and toUTF16z
507 struct CStringImpl(CharType) if (is(CharType: char) || is(CharType: wchar))
508 {
509 public:
510 nothrow:
511 @nogc:
512 
513     const(CharType)* storage = null;
514     alias storage this;
515 
516 
517     this(const(CharType)[] s)
518     {
519         // Always copy. We can't assume anything about the input.
520         size_t len = s.length;
521         CharType* buffer = cast(CharType*) malloc((len + 1) * CharType.sizeof);
522         buffer[0..len] = s[0..len];
523         buffer[len] = '\0';
524         storage = buffer;
525         wasAllocated = true;
526     }
527 
528     // The constructor taking immutable can safely assume that such memory
529     // has been allocated by the GC or malloc, or an allocator that align
530     // pointer on at least 4 bytes.
531     this(immutable(CharType)[] s)
532     {
533         // Same optimizations that for toStringz
534         if (s.empty)
535         {
536             enum emptyString = cast(CharType[])"";
537             storage = emptyString.ptr;
538             return;
539         }
540 
541         /* Peek past end of s[], if it's 0, no conversion necessary.
542         * Note that the compiler will put a 0 past the end of static
543         * strings, and the storage allocator will put a 0 past the end
544         * of newly allocated char[]'s.
545         */
546         const(CharType)* p = s.ptr + s.length;
547         // Is p dereferenceable? A simple test: if the p points to an
548         // address multiple of 4, then conservatively assume the pointer
549         // might be pointing to another block of memory, which might be
550         // unreadable. Otherwise, it's definitely pointing to valid
551         // memory.
552         if ((cast(size_t) p & 3) && *p == 0)
553         {
554             storage = s.ptr;
555             return;
556         }
557 
558         size_t len = s.length;
559         CharType* buffer = cast(CharType*) malloc((len + 1) * CharType.sizeof);
560         buffer[0..len] = s[0..len];
561         buffer[len] = '\0';
562         storage = buffer;
563         wasAllocated = true;
564     }
565 
566     ~this()
567     {
568         if (wasAllocated)
569             free(cast(void*)storage);
570     }
571 
572     @disable this(this);
573 
574 private:
575     bool wasAllocated = false;
576 }
577 
578 
579 //
580 // Launch browser, replaces std.process.browse
581 //
582 
583 void browseNoGC(string url) nothrow @nogc
584 {
585     version(Windows)
586     {
587         import core.sys.windows.winuser;
588         import core.sys.windows.shellapi;
589         ShellExecuteA(null, CString("open").storage, CString(url).storage, null, null, SW_SHOWNORMAL);
590     }
591 
592     version(OSX)
593     {
594         import core.sys.posix.unistd;
595         const(char)*[5] args;
596 
597         auto curl = CString(url).storage;
598         const(char)* browser = getenv("BROWSER");
599         if (browser)
600         {
601             browser = strdup(browser);
602             args[0] = browser;
603             args[1] = curl;
604             args[2] = null;
605         }
606         else
607         {
608             args[0] = "open".ptr;
609             args[1] = curl;
610             args[2] = null;
611         }
612 
613         auto childpid = core.sys.posix.unistd.fork();
614         if (childpid == 0)
615         {
616             core.sys.posix.unistd.execvp(args[0], cast(char**)args.ptr);
617             return;
618         }
619         if (browser)
620             free(cast(void*)browser);
621     }
622 }
623 
624 
625 
626 //
627 // GRAIL SORT IMPLEMENTATION BELOW
628 //
629 // The MIT License (MIT)
630 // 
631 // Copyright (c) 2013 Andrey Astrelin
632 // 
633 // Permission is hereby granted, free of charge, to any person obtaining a copy of
634 // this software and associated documentation files (the "Software"), to deal in
635 // the Software without restriction, including without limitation the rights to
636 // use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
637 // the Software, and to permit persons to whom the Software is furnished to do so,
638 // subject to the following conditions:
639 // 
640 // The above copyright notice and this permission notice shall be included in all
641 // copies or substantial portions of the Software.
642 // 
643 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
644 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
645 // FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
646 // COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
647 // IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
648 // CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
649 
650 private:
651 
652 void grail_swap1(T)(T *a,T *b){
653     T c=*a;
654     *a=*b;
655     *b=c;
656 }
657 void grail_swapN(T)(T *a,T *b,int n){
658     while(n--) grail_swap1(a++,b++);
659 }
660 void grail_rotate(T)(T *a,int l1,int l2){
661     while(l1 && l2){
662         if(l1<=l2){
663             grail_swapN(a,a+l1,l1);
664             a+=l1; l2-=l1;
665         } else{
666             grail_swapN(a+(l1-l2),a+l1,l2);
667             l1-=l2;
668         }
669     }
670 }
671 
672 int grail_BinSearchLeft(T)(T *arr,int len,T *key, nogcComparisonFunction!T comparison){
673     int a=-1,b=len,c;
674     while(a<b-1){
675         c=a+((b-a)>>1);
676         if(comparison(arr[c],*key)>=0) b=c;
677         else a=c;
678     }
679     return b;
680 }
681 int grail_BinSearchRight(T)(T *arr,int len,T *key, nogcComparisonFunction!T comparison){
682     int a=-1,b=len,c;
683     while(a<b-1){
684         c=a+((b-a)>>1);
685         if(comparison(arr[c],*key)>0) b=c;
686         else a=c;
687     }
688     return b;
689 }
690 
691 // cost: 2*len+nk^2/2
692 int grail_FindKeys(T)(T *arr,int len,int nkeys, nogcComparisonFunction!T comparison){
693     int h=1,h0=0;  // first key is always here
694     int u=1,r;
695     while(u<len && h<nkeys){
696         r=grail_BinSearchLeft!T(arr+h0,h,arr+u, comparison);
697         if(r==h || comparison(arr[u],arr[h0+r])!=0){
698             grail_rotate(arr+h0,h,u-(h0+h));
699             h0=u-h;
700             grail_rotate(arr+(h0+r),h-r,1);
701             h++;
702         }
703         u++;
704     }
705     grail_rotate(arr,h0,h);
706     return h;
707 }
708 
709 // cost: min(L1,L2)^2+max(L1,L2)
710 void grail_MergeWithoutBuffer(T)(T *arr,int len1,int len2, nogcComparisonFunction!T comparison){
711     int h;
712     if(len1<len2){
713         while(len1){
714             h=grail_BinSearchLeft!T(arr+len1,len2,arr, comparison);
715             if(h!=0){
716                 grail_rotate(arr,len1,h);
717                 arr+=h;
718                 len2-=h;
719             }
720             if(len2==0) break;
721             do{
722                 arr++; len1--;
723             } while(len1 && comparison(*arr,arr[len1])<=0);
724         }
725     } else{
726         while(len2){
727             h=grail_BinSearchRight!T(arr,len1,arr+(len1+len2-1), comparison);
728             if(h!=len1){
729                 grail_rotate(arr+h,len1-h,len2);
730                 len1=h;
731             }
732             if(len1==0) break;
733             do{
734                 len2--;
735             } while(len2 && comparison(arr[len1-1],arr[len1+len2-1])<=0);
736         }
737     }
738 }
739 
740 // arr[M..-1] - buffer, arr[0,L1-1]++arr[L1,L1+L2-1] -> arr[M,M+L1+L2-1]
741 void grail_MergeLeft(T)(T *arr,int L1,int L2,int M, nogcComparisonFunction!T comparison){
742     int p0=0,p1=L1; L2+=L1;
743     while(p1<L2){
744         if(p0==L1 || comparison(arr[p0],arr[p1])>0){
745             grail_swap1(arr+(M++),arr+(p1++));
746         } else{
747             grail_swap1(arr+(M++),arr+(p0++));
748         }
749     }
750     if(M!=p0) grail_swapN(arr+M,arr+p0,L1-p0);
751 }
752 void grail_MergeRight(T)(T *arr,int L1,int L2,int M, nogcComparisonFunction!T comparison){
753     int p0=L1+L2+M-1,p2=L1+L2-1,p1=L1-1;
754 
755     while(p1>=0){
756         if(p2<L1 || comparison(arr[p1],arr[p2])>0){
757             grail_swap1(arr+(p0--),arr+(p1--));
758         } else{
759             grail_swap1(arr+(p0--),arr+(p2--));
760         }
761     }
762     if(p2!=p0) while(p2>=L1) grail_swap1(arr+(p0--),arr+(p2--));
763 }
764 
765 void grail_SmartMergeWithBuffer(T)(T *arr,int *alen1,int *atype,int len2,int lkeys, nogcComparisonFunction!T comparison){
766     int p0=-lkeys,p1=0,p2=*alen1,q1=p2,q2=p2+len2;
767     int ftype=1-*atype;  // 1 if inverted
768     while(p1<q1 && p2<q2){
769         if(comparison(arr[p1],arr[p2])-ftype<0) grail_swap1(arr+(p0++),arr+(p1++));
770         else grail_swap1(arr+(p0++),arr+(p2++));
771     }
772     if(p1<q1){
773         *alen1=q1-p1;
774         while(p1<q1) grail_swap1(arr+(--q1),arr+(--q2));
775     } else{
776         *alen1=q2-p2;
777         *atype=ftype;
778     }
779 }
780 void grail_SmartMergeWithoutBuffer(T)(T *arr,int *alen1,int *atype,int _len2, nogcComparisonFunction!T comparison){
781     int len1,len2,ftype,h;
782     
783     if(!_len2) return;
784     len1=*alen1;
785     len2=_len2;
786     ftype=1-*atype;
787     if(len1 && comparison(arr[len1-1],arr[len1])-ftype>=0){
788         while(len1){
789             h=ftype ? grail_BinSearchLeft!T(arr+len1,len2,arr, comparison) : grail_BinSearchRight!T(arr+len1,len2,arr, comparison);
790             if(h!=0){
791                 grail_rotate(arr,len1,h);
792                 arr+=h;
793                 len2-=h;
794             }
795             if(len2==0){
796                 *alen1=len1;
797                 return;
798             }
799             do{
800                 arr++; len1--;
801             } while(len1 && comparison(*arr,arr[len1])-ftype<0);
802         }
803     }
804     *alen1=len2; *atype=ftype;
805 }
806 
807 /***** Sort With Extra Buffer *****/
808 
809 // arr[M..-1] - free, arr[0,L1-1]++arr[L1,L1+L2-1] -> arr[M,M+L1+L2-1]
810 void grail_MergeLeftWithXBuf(T)(T *arr,int L1,int L2,int M, nogcComparisonFunction!T comparison){
811     int p0=0,p1=L1; L2+=L1;
812     while(p1<L2){
813         if(p0==L1 || comparison(arr[p0],arr[p1])>0) arr[M++]=arr[p1++];
814         else arr[M++]=arr[p0++];
815     }
816     if(M!=p0) while(p0<L1) arr[M++]=arr[p0++];
817 }
818 
819 void grail_SmartMergeWithXBuf(T)(T *arr,int *alen1,int *atype,int len2,int lkeys, nogcComparisonFunction!T comparison){
820     int p0=-lkeys,p1=0,p2=*alen1,q1=p2,q2=p2+len2;
821     int ftype=1-*atype;  // 1 if inverted
822     while(p1<q1 && p2<q2){
823         if(comparison(arr[p1],arr[p2])-ftype<0) arr[p0++]=arr[p1++];
824         else arr[p0++]=arr[p2++];
825     }
826     if(p1<q1){
827         *alen1=q1-p1;
828         while(p1<q1) arr[--q2]=arr[--q1];
829     } else{
830         *alen1=q2-p2;
831         *atype=ftype;
832     }
833 }
834 
835 // arr - starting array. arr[-lblock..-1] - buffer (if havebuf).
836 // lblock - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded
837 // keys - arrays of keys, in same order as blocks. key<midkey means stream A
838 // nblock2 are regular blocks from stream A. llast is length of last (irregular) block from stream B, that should go before nblock2 blocks.
839 // llast=0 requires nblock2=0 (no irregular blocks). llast>0, nblock2=0 is possible.
840 void grail_MergeBuffersLeftWithXBuf(T)(T *keys,T *midkey,T *arr,int nblock,int lblock,int nblock2,int llast, nogcComparisonFunction!T comparison){
841     int l,prest,lrest,frest,pidx,cidx,fnext,plast;
842 
843     if(nblock==0){
844         l=nblock2*lblock;
845         grail_MergeLeftWithXBuf!T(arr,l,llast,-lblock, comparison);
846         return;
847     }
848 
849     lrest=lblock;
850     frest=comparison(*keys,*midkey)<0 ? 0 : 1;
851     pidx=lblock;
852     for(cidx=1;cidx<nblock;cidx++,pidx+=lblock){
853         prest=pidx-lrest;
854         fnext=comparison(keys[cidx],*midkey)<0 ? 0 : 1;
855         if(fnext==frest){
856             memcpy(arr+prest-lblock,arr+prest,lrest*T.sizeof);
857             prest=pidx;
858             lrest=lblock;
859         } else{
860             grail_SmartMergeWithXBuf!T(arr+prest,&lrest,&frest,lblock,lblock, comparison);
861         }
862     }
863     prest=pidx-lrest;
864     if(llast){
865         plast=pidx+lblock*nblock2;
866         if(frest){
867             memcpy(arr+prest-lblock,arr+prest,lrest*T.sizeof);
868             prest=pidx;
869             lrest=lblock*nblock2;
870             frest=0;
871         } else{
872             lrest+=lblock*nblock2;
873         }
874         grail_MergeLeftWithXBuf!T(arr+prest,lrest,llast,-lblock, comparison);
875     } else{
876         memcpy(arr+prest-lblock,arr+prest,lrest*T.sizeof);
877     }
878 }
879 
880 /***** End Sort With Extra Buffer *****/
881 
882 // build blocks of length K
883 // input: [-K,-1] elements are buffer
884 // output: first K elements are buffer, blocks 2*K and last subblock sorted
885 void grail_BuildBlocks(T)(T *arr,int L,int K,T *extbuf,int LExtBuf, nogcComparisonFunction!T comparison){
886     int m,u,h,p0,p1,rest,restk,p,kbuf;
887     kbuf=K<LExtBuf ? K : LExtBuf;
888     while(kbuf&(kbuf-1)) kbuf&=kbuf-1;  // max power or 2 - just in case
889 
890     if(kbuf){
891         memcpy(extbuf,arr-kbuf,kbuf*T.sizeof);
892         for(m=1;m<L;m+=2){
893             u=0;
894             if(comparison(arr[m-1],arr[m])>0) u=1;
895             arr[m-3]=arr[m-1+u];
896             arr[m-2]=arr[m-u];
897         }
898         if(L%2) arr[L-3]=arr[L-1];
899         arr-=2;
900         for(h=2;h<kbuf;h*=2){
901             p0=0;
902             p1=L-2*h;
903             while(p0<=p1){
904                 grail_MergeLeftWithXBuf!T(arr+p0,h,h,-h, comparison);
905                 p0+=2*h;
906             }
907             rest=L-p0;
908             if(rest>h){
909                 grail_MergeLeftWithXBuf!T(arr+p0,h,rest-h,-h, comparison);
910             } else {
911                 for(;p0<L;p0++) arr[p0-h]=arr[p0];
912             }
913             arr-=h;
914         }
915         memcpy(arr+L,extbuf,kbuf*T.sizeof);
916     } else{
917         for(m=1;m<L;m+=2){
918             u=0;
919             if(comparison(arr[m-1],arr[m])>0) u=1;
920             grail_swap1(arr+(m-3),arr+(m-1+u));
921             grail_swap1(arr+(m-2),arr+(m-u));
922         }
923         if(L%2) grail_swap1(arr+(L-1),arr+(L-3));
924         arr-=2;
925         h=2;
926     }
927     for(;h<K;h*=2){
928         p0=0;
929         p1=L-2*h;
930         while(p0<=p1){
931             grail_MergeLeft!T(arr+p0,h,h,-h, comparison);
932             p0+=2*h;
933         }
934         rest=L-p0;
935         if(rest>h){
936             grail_MergeLeft!T(arr+p0,h,rest-h,-h, comparison);
937         } else grail_rotate(arr+p0-h,h,rest);
938         arr-=h;
939     }
940     restk=L%(2*K);
941     p=L-restk;
942     if(restk<=K) grail_rotate(arr+p,restk,K);
943     else grail_MergeRight!T(arr+p,K,restk-K,K, comparison);
944     while(p>0){
945         p-=2*K;
946         grail_MergeRight!T(arr+p,K,K,K, comparison);
947     }
948 }
949 
950 // arr - starting array. arr[-lblock..-1] - buffer (if havebuf).
951 // lblock - length of regular blocks. First nblocks are stable sorted by 1st elements and key-coded
952 // keys - arrays of keys, in same order as blocks. key<midkey means stream A
953 // nblock2 are regular blocks from stream A. llast is length of last (irregular) block from stream B, that should go before nblock2 blocks.
954 // llast=0 requires nblock2=0 (no irregular blocks). llast>0, nblock2=0 is possible.
955 void grail_MergeBuffersLeft(T)(T *keys,T *midkey,T *arr,int nblock,int lblock,bool havebuf,int nblock2,int llast, nogcComparisonFunction!T comparison){
956     int l,prest,lrest,frest,pidx,cidx,fnext,plast;
957     
958     if(nblock==0){
959         l=nblock2*lblock;
960         if(havebuf) grail_MergeLeft!T(arr,l,llast,-lblock, comparison);
961         else grail_MergeWithoutBuffer!T(arr,l,llast, comparison);
962         return;
963     }
964 
965     lrest=lblock;
966     frest=comparison(*keys,*midkey)<0 ? 0 : 1;
967     pidx=lblock;
968     for(cidx=1;cidx<nblock;cidx++,pidx+=lblock){
969         prest=pidx-lrest;
970         fnext=comparison(keys[cidx],*midkey)<0 ? 0 : 1;
971         if(fnext==frest){
972             if(havebuf) grail_swapN(arr+prest-lblock,arr+prest,lrest);
973             prest=pidx;
974             lrest=lblock;
975         } else{
976             if(havebuf){
977                 grail_SmartMergeWithBuffer!T(arr+prest,&lrest,&frest,lblock,lblock, comparison);
978             } else{
979                 grail_SmartMergeWithoutBuffer!T(arr+prest,&lrest,&frest,lblock, comparison);
980             }
981 
982         }
983     }
984     prest=pidx-lrest;
985     if(llast){
986         plast=pidx+lblock*nblock2;
987         if(frest){
988             if(havebuf) grail_swapN(arr+prest-lblock,arr+prest,lrest);
989             prest=pidx;
990             lrest=lblock*nblock2;
991             frest=0;
992         } else{
993             lrest+=lblock*nblock2;
994         }
995         if(havebuf) grail_MergeLeft!T(arr+prest,lrest,llast,-lblock, comparison);
996         else grail_MergeWithoutBuffer!T(arr+prest,lrest,llast, comparison);
997     } else{
998         if(havebuf) grail_swapN(arr+prest,arr+(prest-lblock),lrest);
999     }
1000 }
1001 
1002 void grail_SortIns(T)(T *arr,int len, nogcComparisonFunction!T comparison){
1003     int i,j;
1004     for(i=1;i<len;i++){
1005         for(j=i-1;j>=0 && comparison(arr[j+1],arr[j])<0;j--) grail_swap1(arr+j,arr+(j+1));
1006     }
1007 }
1008 
1009 void grail_LazyStableSort(T)(T *arr,int L, nogcComparisonFunction!T comparison){
1010     int m,u,h,p0,p1,rest;
1011     for(m=1;m<L;m+=2){
1012         u=0;
1013         if(comparison(arr[m-1],arr[m])>0) grail_swap1(arr+(m-1),arr+m);
1014     }
1015     for(h=2;h<L;h*=2){
1016         p0=0;
1017         p1=L-2*h;
1018         while(p0<=p1){
1019             grail_MergeWithoutBuffer!T(arr+p0,h,h, comparison);
1020             p0+=2*h;
1021         }
1022         rest=L-p0;
1023         if(rest>h) grail_MergeWithoutBuffer!T(arr+p0,h,rest-h, comparison);
1024     }
1025 }
1026 
1027 // keys are on the left of arr. Blocks of length LL combined. We'll combine them in pairs
1028 // LL and nkeys are powers of 2. (2*LL/lblock) keys are guarantied
1029 void grail_CombineBlocks(T)(T *keys,T *arr,int len,int LL,int lblock,bool havebuf,T *xbuf, nogcComparisonFunction!T comparison){
1030     int M,nkeys,b,NBlk,midkey,lrest,u,p,v,kc,nbl2,llast;
1031     T *arr1;
1032     
1033     M=len/(2*LL);
1034     lrest=len%(2*LL);
1035     nkeys=(2*LL)/lblock;
1036     if(lrest<=LL){
1037         len-=lrest;
1038         lrest=0;
1039     }
1040     if(xbuf) memcpy(xbuf,arr-lblock,lblock*T.sizeof);
1041     for(b=0;b<=M;b++){
1042         if(b==M && lrest==0) break;
1043         arr1=arr+b*2*LL;
1044         NBlk=(b==M ? lrest : 2*LL)/lblock;
1045         grail_SortIns!T(keys,NBlk+(b==M ? 1 : 0), comparison);
1046         midkey=LL/lblock;
1047         for(u=1;u<NBlk;u++){
1048             p=u-1;
1049             for(v=u;v<NBlk;v++){
1050                 kc=comparison(arr1[p*lblock],arr1[v*lblock]);
1051                 if(kc>0 || (kc==0 && comparison(keys[p],keys[v])>0)) p=v;
1052             }
1053             if(p!=u-1){
1054                 grail_swapN(arr1+(u-1)*lblock,arr1+p*lblock,lblock);
1055                 grail_swap1(keys+(u-1),keys+p);
1056                 if(midkey==u-1 || midkey==p) midkey^=(u-1)^p;
1057             }
1058         }
1059         nbl2=llast=0;
1060         if(b==M) llast=lrest%lblock;
1061         if(llast!=0){
1062             while(nbl2<NBlk && comparison(arr1[NBlk*lblock],arr1[(NBlk-nbl2-1)*lblock])<0) nbl2++;
1063         }
1064         if(xbuf) grail_MergeBuffersLeftWithXBuf!T(keys,keys+midkey,arr1,NBlk-nbl2,lblock,nbl2,llast, comparison);
1065         else grail_MergeBuffersLeft!T(keys,keys+midkey,arr1,NBlk-nbl2,lblock,havebuf,nbl2,llast, comparison);
1066     }
1067     if(xbuf){
1068         for(p=len;--p>=0;) arr[p]=arr[p-lblock];
1069         memcpy(arr-lblock,xbuf,lblock*T.sizeof);
1070     }else if(havebuf) while(--len>=0) grail_swap1(arr+len,arr+len-lblock);
1071 }
1072 
1073 
1074 void grail_commonSort(T)(T *arr,int Len,T *extbuf,int LExtBuf, nogcComparisonFunction!T comparison){
1075     int lblock,nkeys,findkeys,ptr,cbuf,lb,nk;
1076     bool havebuf,chavebuf;
1077     long s;
1078     
1079     if(Len<16){
1080         grail_SortIns!T(arr,Len, comparison);
1081         return;
1082     }
1083 
1084     lblock=1;
1085     while(lblock*lblock<Len) lblock*=2;
1086     nkeys=(Len-1)/lblock+1;
1087     findkeys=grail_FindKeys!T(arr,Len,nkeys+lblock, comparison);
1088     havebuf=true;
1089     if(findkeys<nkeys+lblock){
1090         if(findkeys<4){
1091             grail_LazyStableSort!T(arr,Len, comparison);
1092             return;
1093         }
1094         nkeys=lblock;
1095         while(nkeys>findkeys) nkeys/=2;
1096         havebuf=false;
1097         lblock=0;
1098     }
1099     ptr=lblock+nkeys;
1100     cbuf=havebuf ? lblock : nkeys;
1101     if(havebuf) grail_BuildBlocks!T(arr+ptr,Len-ptr,cbuf,extbuf,LExtBuf, comparison);
1102     else grail_BuildBlocks!T(arr+ptr,Len-ptr,cbuf,null,0, comparison);
1103 
1104     // 2*cbuf are built
1105     while(Len-ptr>(cbuf*=2)){
1106         lb=lblock;
1107         chavebuf=havebuf;
1108         if(!havebuf){
1109             if(nkeys>4 && nkeys/8*nkeys>=cbuf){
1110                 lb=nkeys/2;
1111                 chavebuf=true;
1112             } else{
1113                 nk=1;
1114                 s=cast(long)cbuf*findkeys/2;
1115                 while(nk<nkeys && s!=0){
1116                     nk*=2; s/=8;
1117                 }
1118                 lb=(2*cbuf)/nk;
1119             }
1120         }
1121         grail_CombineBlocks!T(arr,arr+ptr,Len-ptr,cbuf,lb,chavebuf,chavebuf && lb<=LExtBuf ? extbuf : null, comparison);
1122     }
1123     grail_SortIns!T(arr,ptr, comparison);
1124     grail_MergeWithoutBuffer!T(arr,ptr,Len-ptr, comparison);
1125 }
1126 
1127 void GrailSort(T)(T *arr, int Len, nogcComparisonFunction!T comparison){
1128     grail_commonSort!T(arr,Len,null,0, comparison);
1129 }
1130 
1131 void GrailSortWithBuffer(T)(T *arr,int Len, nogcComparisonFunction!T comparison){
1132     T[128] ExtBuf;
1133     grail_commonSort!T(arr,Len,ExtBuf.ptr,128, comparison);
1134 }
1135 
1136 /****** classic MergeInPlace *************/
1137 
1138 void grail_RecMerge(T)(T *A,int L1,int L2, nogcComparisonFunction!T comparison){
1139     int K,k1,k2,m1,m2;
1140     if(L1<3 || L2<3){
1141         grail_MergeWithoutBuffer(A,L1,L2); return;
1142     }
1143     if(L1<L2) K=L1+L2/2;
1144     else K=L1/2;
1145     k1=k2=grail_BinSearchLeft(A,L1,A+K);
1146     if(k2<L1 && comparison(A+k2,A+K)==0) k2=grail_BinSearchRight(A+k1,L1-k1,A+K)+k1;
1147     m1=grail_BinSearchLeft(A+L1,L2,A+K);
1148     m2=m1;
1149     if(m2<L2 && comparison(A+L1+m2,A+K)==0) m2=grail_BinSearchRight(A+L1+m1,L2-m1,A+K)+m1;
1150     if(k1==k2) grail_rotate(A+k2,L1-k2,m2);
1151     else{
1152         grail_rotate(A+k1,L1-k1,m1);
1153         if(m2!=m1) grail_rotate(A+(k2+m1),L1-k2,m2-m1);
1154     }
1155     grail_RecMerge(A+(k2+m2),L1-k2,L2-m2);
1156     grail_RecMerge(A,k1,m1);
1157 }
1158 void RecStableSort(T)(T *arr,int L){
1159     int u,m,h,p0,p1,rest;
1160 
1161     for(m=1;m<L;m+=2){
1162         u=0;
1163         if(comparison(arr+m-1,arr+m)>0) grail_swap1(arr+(m-1),arr+m);
1164     }
1165     for(h=2;h<L;h*=2){
1166         p0=0;
1167         p1=L-2*h;
1168         while(p0<=p1){
1169             grail_RecMerge(arr+p0,h,h);
1170             p0+=2*h;
1171         }
1172         rest=L-p0;
1173         if(rest>h) grail_RecMerge(arr+p0,h,rest-h);
1174     }
1175 }