www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - "No stack address"

reply Somedude <lovelydear mailmetrash.com> writes:
I'm trying to compile a D source on win32 with DMD 2.059, and I get this:

PS E:\DigitalMars\dmd2\samples> rdmd xinoksort.d
OPTLINK (R) for Win32  Release 8.00.12
Copyright (C) Digital Mars 1989-2010  All rights reserved.
http://www.digitalmars.com/ctg/optlink.html
OPTLINK : Warning 23: No Stack
OPTLINK : Warning 134: No Start Address
PS E:\DigitalMars\dmd2\samples>

Clearly, the link phase didn't complete correctly:

-a---        16/04/2012     08:55      12600 xinoksort.d
-a---        16/04/2012     21:12         56 xinoksort.exe
-a---        16/04/2012     21:12        889 xinoksort.obj

Phobos wasn't linked. What happened ?
Does it link dynamically now ? How do I set the libpath (I'm using the
Powershell) ?
Apr 16 2012
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 4/16/12, Somedude <lovelydear mailmetrash.com> wrote:

 OPTLINK : Warning 134: No Start Address


This means you're missing a void main or int main function. You can
pass  --main to rdmd to add it automatically (useful when e.g.
unittesting).
Apr 16 2012
parent reply Somedude <lovelydear mailmetrash.com> writes:
Le 16/04/2012 21:51, Andrej Mitrovic a écrit :

 On 4/16/12, Somedude <lovelydear mailmetrash.com> wrote:

 OPTLINK : Warning 134: No Start Address


 
 This means you're missing a void main or int main function. You can
 pass  --main to rdmd to add it automatically (useful when e.g.
 unittesting).


All right, now I have a bunch of questions.
Sorry, D newcomer here.

I hate to do this, but I'll simply dump the full code, it should save me
a lot of questions.

/++
	Xinok Sort for the D Programming Language
	
	Written and tested for DMD 2.055 and Phobos
	
	Authors:  Xinok
	Date:     November 2011
	License:  Public Domain
	Web:      $(LINK http://www.sourceforge.net/projects/xinoksort)
	
	Todo:
	Parallelization - Write a separate function which runs xinok sort in
multiple threads
	
	Support for CTFE - Sorting arrays at compile time
	
	Unittest for ranges - Test implementation of xinok sort using range
primitives
	
	In / Out conditions and asserts
++/

module xinoksort;
import std.range;
import std.functional : binaryFun, not;
import std.algorithm : swap, swapRanges, copy, reverse, isSorted;
import std.traits : isCallable;
import core.exception : OutOfMemoryError;

/++
	This function will sort an array or range in-place,
	optionally using a custom predicate.
	
	Returns: Sorted input as SortedRange
	
	Throws: OutOfMemoryError if memory allocation fails
	
	Predicate:
	The predicate can be a string, function, or delegate.
	
	A string should represent the two elements to compare
	using the characters 'a' and 'b'.
	
	A function or delegate should take two arguments of the
	same type and return a bool.
	
	The default predicate for sorting is "a < b".
	
	Examples:
	---
	int[] arr = [20, 40, 60, 10, 30, 50];
	xinokSort(arr);
	
	// Sort in reverse order
	xinokSort!("a > b")(arr);
	
	// Use a function or delegate as predicate
	bool comp(int a, int b){ return a < b; }
	xinokSort!(comp)(arr);
	
	// Sort an array of strings, case insensitive
	string[] list;
	xinokSort!("icmp(a, b) < 0")(list);
	---
++/
SortedRange!(Range, pred) xinokSort(alias pred = "a < b", Range)(Range arr){
	typeof(Range[0])[] temp;
	
	if(!__ctfe){ // Allocate temporary memory
		size_t len = arr.length >= 1024*64 ? arr.length / 1024 : 64;
		while(temp is null){
			try temp.length = len;
			catch(OutOfMemoryError err){ // Reduce memory usage and try again
				len /= 2;
				if(len >= 8) continue;
				else throw err;
			}
		}
	}
	else temp.length = 1024;
	
	XinokSortImpl!(pred, Range).findRuns(arr, arr.length, temp);
	return assumeSorted!(pred, Range)(arr);
}

/++ Generate compare functions from predicate

    Example:
    ---
    mixin Compares!("a > b");
    ---
++/
template Compares(alias pred){
	static if(is(typeof(pred) : string)){
		alias binaryFun!(pred) less;
		alias binaryFun!(pred, "b", "a") greater;
		alias not!(binaryFun!(pred)) greaterEqual;
		alias not!(binaryFun!(pred, "b", "a")) lessEqual;
	}
	else static if(isCallable!pred){
		alias pred less;
		auto greater(T)(T a, T b){ return pred(b, a); }
		auto greaterEqual(T)(T a, T b){ return !pred(a, b); }
		auto lessEqual(T)(T a, T b){ return !pred(b, a); }
	}
	else static assert(false, "Invalid predicate");
}

/// Implementation of xinok sort for ranges
template XinokSortImpl(alias pred, Range){
	static assert(isRandomAccessRange!Range && isBidirectionalRange!Range
&& hasSlicing!Range, Range.toString ~ " is incompatible with xinok sort");
	
	alias typeof(Range[0]) T;
	mixin Compares!pred;
	
	/// Find runs in ascending or descending order and merge them
	size_t findRuns(Range arr, size_t t, T[] temp){
		enum min_run = 8;
		
		if(arr.length <= min_run){
			insertSort(arr);
			return arr.length;
		}
		
		if(t > arr.length) t = arr.length;
		
		// Find first run
		size_t lef = 2;
		if(lessEqual(arr[0], arr[1])){ // Ascending order
			while(lef < arr.length && lessEqual(arr[lef-1], arr[lef])) ++lef;
		}
		else{ // Descending order
			while(lef < arr.length && greater(arr[lef-1], arr[lef])) ++lef;
			
			// reverse(arr[0..lef]);
			auto tmp = arr[0..lef];
			while(tmp.length >= 2){
				swap(tmp.front, tmp.back);
				tmp = tmp[1..$-1];
			}
		}
		
		if(lef < min_run){ // Build run of min length
			insertSort(arr[0..min_run]);
			lef = min_run;
		}
		
		while(lef < t){ // Build run of length t
			size_t rig = findRuns(arr[lef..$], lef, temp) + lef;
			mergeRuns(arr[0..rig], arr[0..lef], arr[lef..rig], temp);
			lef = rig;
		}
		
		return lef;
	}
	
	/// Merge together two sorted runs
	void mergeRuns(Range arr, Range lef, Range rig, T[] temp){
		assert(arr.length == lef.length + rig.length);
		
		if(lef.length <= rig.length){
			if(lef.length == 0) return; // Nothing to do
			
			if(lef.length <= temp.length){ // Merge left to right
				copy(lef, temp[0..lef.length]);
				lef = temp[0..lef.length];
				
				foreach(ref v; arr){
					if(lessEqual(lef.front, rig.front)){
						v = lef.front;
						lef.popFront();
						if(lef.empty) break;
					}
					else{
						v = rig.front;
						rig.popFront();
						if(rig.empty) break;
					}
				}
				if(!lef.empty) copy(lef, arr[$-lef.length .. $]);
			}
			else{ // Range Swap
				if(lessEqual(lef.back, rig.front)) return; // Nothing to swap
				
				size_t c;
				{
					// Binary search
					size_t l = 0, u = lef.length - 1;
					immutable off = lef.length - 1;
					while(u - l > 1){
						c = (u - l) / 2 + l;
						if(greater(lef[c], rig[off-c])) u = c;
						else l = c;
					}
					c = greater(lef[l], rig[off-l]) ? l : u;
					
					// swapRanges(lef[c..$], rig[0..off-c+1]);
					foreach(i, ref v; lef[c..$]) swap(v, rig[i]);
				}
				
				mergeRuns(lef, lef[0..c], lef[c..$], temp);
				return mergeRuns(rig, rig[0..lef.length-c], rig[lef.length-c..$], temp);
			}
		}
		else{
			if(rig.length == 0) return; // Nothing to do
			
			if(rig.length <= temp.length){ // Merge right to left
				copy(rig, temp[0..rig.length]);
				rig = temp[0..rig.length];
				
				foreach_reverse(ref v; arr){
					if(greaterEqual(rig.back, lef.back)){
						v = rig.back;
						rig.popBack();
						if(rig.empty) break;
					}
					else{
						v = lef.back;
						lef.popBack();
						if(lef.empty) break;
					}
				}
				if(!rig.empty) copy(rig, arr[0..rig.length]);
			}
			else{ // Range Swap
				if(lessEqual(lef.back, rig.front)) return; // Nothing to swap
				
				size_t c;
				{
					// Binary search
					size_t l = 0, u = rig.length - 1;
					immutable off = lef.length - 1;
					while(u - l > 1){
						c = (u - l) / 2 + l;
						if(less(rig[c], lef[off-c])) l = c;
						else u = c;
					}
					c = less(rig[u], lef[off-u]) ? u : l;
					
					// swapRanges(lef[off-c..$], rig[0..c+1]);
					foreach(i, ref v; lef[off-c..$]) swap(v, rig[i]);
				}
				
				mergeRuns(rig, rig[0..c + 1], rig[c + 1..$], temp);
				return mergeRuns(lef, lef[0..$-1-c], lef[$-1-c..$], temp);
			}
		}
	}

	/// A simple insert sort used for obtaining min_run
	void insertSort(Range arr){
		T o; size_t j;
		for(size_t i = 1; i < arr.length; ++i) if(less(arr[i], arr[i-1])){
			j = i; o = arr[j];
			do{
				arr[j] = arr[j-1];
				--j;
			} while(j >= 1 && less(o, arr[j-1]));
			arr[j] = o;
		}
	}
}


/// Implementation of xinok sort for arrays
template XinokSortImpl(alias pred, T : T[]){
	alias T[] Range;
	mixin Compares!pred;
	
	/// Find runs in ascending or descending order and merge them
	size_t findRuns(Range arr, size_t t, T[] temp){
		enum min_run = 8;
		
		if(arr.length <= min_run){
			insertSort(arr);
			return arr.length;
		}
		
		if(t > arr.length) t = arr.length;
		
		// Find first run
		size_t lef = 2;
		if(lessEqual(arr[0], arr[1])){ // Ascending order
			auto p = arr.ptr + 2, e = arr.ptr + arr.length;
			while(p < e && lessEqual(p[-1], *p)) ++p;
			lef = p - arr.ptr;
		}
		else{ // Descending order
			auto p = arr.ptr + 2, e = arr.ptr + arr.length;
			while(p < e && greater(p[-1], *p)) ++p;
			lef = p - arr.ptr;
			
			// Reverse elements
			e = arr.ptr; --p;
			while(e < p) swap(*e++, *p--);
		}
		
		if(lef < min_run){ // Build run of min length
			insertSort(arr[0..min_run]);
			lef = min_run;
		}
		
		while(lef < t){ // Build run of length t
			size_t rig = findRuns(arr[lef..$], lef, temp) + lef;
			mergeRuns(arr[0..rig], arr[0..lef], arr[lef..rig], temp);
			lef = rig;
		}
		
		return lef;
	}
		
	/// Merge together two sorted runs
	void mergeRuns(Range arr, Range lef, Range rig, T[] temp){
		assert(arr.length == lef.length + rig.length);
		
		if(lef.length <= rig.length){
			if(lef.length == 0) return; // Nothing to do
			
			if(lef.length <= temp.length){ // Merge left to right
				// copy(lef, temp[0..lef.length]);
				temp[0..lef.length] = lef[];
				
				T* p = arr.ptr;
                T* l = temp.ptr, l_end = temp.ptr + lef.length;
                T* r = rig.ptr, r_end = rig.ptr + rig.length;
				while(true){
					if(lessEqual(*l, *r)){
						*p++ = *l++;
						if(l >= l_end) break;
					}
					else{
						*p++ = *r++;
						if(r >= r_end) break;
					}
				}
				while(l < l_end) *p++ = *l++;
			}
			else{ // Range Swap
				if(lessEqual(lef[$-1], rig[0])) return; // Nothing to swap
				
				size_t c;
				{
					// Binary search
					size_t l = 0, u = lef.length - 1;
					immutable off = lef.length - 1;
					while(u - l > 1){
						c = (u - l) / 2 + l;
						if(greater(lef[c], rig[off-c])) u = c;
						else l = c;
					}
					c = greater(lef[l], rig[off-l]) ? l : u;
					
					// Swap elements
					T* lp = lef.ptr + lef.length - 1;
					T* rp = rig.ptr + (off - c);
					T o;
					while(rp >= rig.ptr){
						o = *lp;
						*lp = *rp;
						*rp = o;
						--lp; --rp;
					}
				}
				
				mergeRuns(lef, lef[0..c], lef[c..$], temp);
				return mergeRuns(rig, rig[0..lef.length-c], rig[lef.length-c..$], temp);
			}
		}
		else{
			if(rig.length == 0) return; // Nothing to do
			
			if(rig.length <= temp.length){ // Merge right to left
				// copy(rig, temp[0..rig.length]);
				temp[0..rig.length] = rig[];
				
				T* p = arr.ptr + arr.length - 1, l = lef.ptr + lef.length - 1, r =
temp.ptr + rig.length - 1;
				while(true){
					if(greaterEqual(*r, *l)){
						*p-- = *r--;
						if(r < temp.ptr) break;
					}
					else{
						*p-- = *l--;
						if(l < lef.ptr) break;
					}
				}
				while(r >= temp.ptr) *p-- = *r--;
			}
			else{ // Range Swap
				if(lessEqual(lef[$-1], rig[0])) return; // Nothing to swap
				
				size_t c;
				{
					// Binary search
					size_t l = 0, u = rig.length - 1;
					immutable off = lef.length - 1;
					while(u - l > 1){
						c = (u - l) / 2 + l;
						if(less(rig[c], lef[off-c])) l = c;
						else u = c;
					}
					c = less(rig[u], lef[off-u]) ? u : l;
					
					// Swap elements
					T* lp = lef.ptr + lef.length - 1;
					T* rp = rig.ptr + c;
					T o;
					while(rp >= rig.ptr){
						o = *lp;
						*lp = *rp;
						*rp = o;
						--lp; --rp;
					}
				}
				
				mergeRuns(rig, rig[0..c + 1], rig[c + 1..$], temp);
				return mergeRuns(lef, lef[0..$-1-c], lef[$-1-c..$], temp);
			}
		}
	}

	/// A simple insert sort used for obtaining min_run
	void insertSort(Range arr){
		T o; T* p;
		foreach(c; arr.ptr + 1 .. arr.ptr + arr.length) if(less(*c, c[-1])){
			p = c; o = *p;
			do{
				*p = p[-1];
				--p;
			} while(p > arr.ptr && less(o, p[-1]));
			*p = o;
		}
	}
}

unittest{
	// Predicate test
	
	bool comp(uint a, uint b){ return a < b; }
	
	with(Compares!comp){
		assert(less(10, 20));
		assert(lessEqual(10, 20));
		assert(!greater(10, 20));
		assert(!greaterEqual(10, 20));
		
		assert(greater(20, 10));
		assert(greaterEqual(20, 10));
		assert(!less(20, 10));
		assert(!lessEqual(20, 10));
		
		assert(!less(10, 10));
		assert(!greater(10, 10));
		assert(lessEqual(10, 10));
		assert(greaterEqual(10, 10));
	}
}

unittest{
	// Sort test
	
	int[] arr = [2, 5, 8, 1, 4, 7, 3, 6, 9];
	xinokSort(arr);
	assert(arr == [1, 2, 3, 4, 5, 6, 7, 8, 9]);
	
	arr = [2, 5, 8, 1, 4, 7, 3, 6, 9];
	xinokSort!("a > b")(arr);
	assert(arr == [9, 8, 7, 6, 5, 4, 3, 2, 1]);
	
	bool comp(int a, int b){ return a > b; }
	arr = [2, 5, 8, 1, 4, 7, 3, 6, 9];
	xinokSort!(comp)(arr);
	assert(arr == [9, 8, 7, 6, 5, 4, 3, 2, 1]);
	
	// Stability test
	
	bool icmp(ubyte a, ubyte b){
		if(a >= 'a') a -= 'a' - 'A';
		if(b >= 'a') b -= 'a' - 'A';
		return a < b;
	}
	ubyte[] str =
cast(ubyte[])"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".dup;
	xinokSort!(icmp)(str);
	assert(str == "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");
	
	// CTFE test
	
	int[] foo(){
		int[] tmp = [20, 40, 60, 80, 10, 30, 50, 70, 90];
		xinokSort(tmp);
		return tmp;
	}
	//  static assert(foo() == [10, 20, 30, 40, 50, 60, 70, 80, 90]);
}


All I want is compile and run this.
Everything is there, the unit test included. I thought that should have
been sufficient to be a runnable program.

Basically, if I type
PS E:\DigitalMars\dmd2\samples> rdmd --main xinoksort.d
Now it compiles and links without warning, and I get:

-a---        16/04/2012     08:55      12600 xinoksort.d
-a---        16/04/2012     22:34       3621 xinoksort.d.deps
-a---        16/04/2012     22:34      13264 xinoksort.exe
-a---        16/04/2012     22:34      38763 xinoksort.obj

But running the exe crashes immediately at execution with "unauthorized
instruction". Why ? Shouldn't it run, do nothing and quit nicely ?

And how do I execute the unit test ?
I'm sorry for all these questions, but it appears to be hard to find
these simple infos in the wiki and main website. I guess I'll update the
wiki to make it convenient to find them.
Apr 16 2012
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 4/17/12, Somedude <lovelydear mailmetrash.com> wrote:

 But running the exe crashes immediately at execution with "unauthorized
 instruction". Why ?


That's the old exectuable leftover from the previous compile. RDMD
generates the exe in a temporary folder with a random name and runs it
immediately. Because the main function doesn't do anything (RDMD
provides an empty one via --main), the app exited immediately.


 And how do I execute the unit test ?


rdmd -unittest --main test.d
Apr 16 2012
parent reply Somedude <lovelydear mailmetrash.com> writes:
Le 17/04/2012 01:26, Andrej Mitrovic a écrit :

 On 4/17/12, Somedude <lovelydear mailmetrash.com> wrote:

 But running the exe crashes immediately at execution with "unauthorized
 instruction". Why ?


 
 That's the old exectuable leftover from the previous compile. RDMD
 generates the exe in a temporary folder with a random name and runs it
 immediately. Because the main function doesn't do anything (RDMD
 provides an empty one via --main), the app exited immediately.
 

 And how do I execute the unit test ?


 
 rdmd -unittest --main test.d


Thanks, it works. BTW, I couldn't find this information. Do you have any
idea where this is explained (in particular the --main switch) that I
overlooked ?
Anyway, I think I'll add this simple piece of info somewhere in the
wiki. I've already cleaned it up a little.
Apr 17 2012
next sibling parent Somedude <lovelydear mailmetrash.com> writes:
Le 17/04/2012 09:30, Somedude a écrit :

 Anyway, I think I'll add this simple piece of info somewhere in the
 wiki. I've already cleaned it up a little.


Ok, here it is: http://prowiki.org/wiki4d/wiki.cgi?HowTo/UnitTests
Apr 17 2012
prev sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 4/17/12, Somedude <lovelydear mailmetrash.com> wrote:

 Do you have any idea where this is explained


rdmd --help
Apr 17 2012