On Fri, Apr 20, 2012 at 08:44:06AM +0400, Denis Shelomovskij wrote:
> 20.04.2012 8:06, H. S. Teoh написал:
> >I'm writing some code that does some very simplistic parsing, and I'm just totally geeking out on how awesome D is for writing such code:
> >
> >	import std.conv;
> >	import std.regex;
> >	import std.stdio;
> >
> >	struct Data {
> >		string name;
> >		string phone;
> >		int age;
> >		... // a whole bunch of other stuff
> >	}
> >
> >	void main() {
> >		Data d;
> >		foreach (line; stdin.byLine()) {
> >			auto m = match(line, "(\w+)\s+(\w+)");
> 
> It's better not to create a regex every iteration. Use e.g.
> ---
> auto regEx = regex(`(\w+)\s+(\w+)`);
> ---
> before foreach. Of course, you are not claiming this as a high-performance program, but creating a regex every iteration is too common mistake to show such code to newbies.

You're right, it was unoptimized code. I ended up using ctRegex for them:

	enum attrRx = ctRegex!`...`;
	enum blockRx = ctRegex!`...`;

	if (auto m = match(line, attrRx)) {
		...
	} else if (auto m = match(line, blockRx)) {
		...
	}

The fact that D enums can be arbitrary types is just beyond awesome.


[...]
> >			auto key = m.captures[1];
> 
> One `.idup` here will be better. (sorry, just like to nitpick)

Yeah you're right. I'm refactoring the code right now, and it's much better to write it this way:

	auto key = m.captures[1].idup;
	auto value = m.captures[2].idup;
	dgs.get(key, invalidAttr)(key, value);

Looks more concise, too.

[...]
> A shorter variant:
> ---
> void delegate(string, string)[string] dgs = [
> 	"name" : (key, value) { d.name = value; },
> 	"phone": (key, value) { d.phone = value; },
> 	"age"  : (key, value) { d.age = to!int(value); },
> 	...	// whole bunch of other stuff to
> 		// parse different attributes
> ];
[...]

Good idea, I really need to work on my delegate syntax. I must admit I still have to look it up each time, 'cos I just can't remember the right syntax with all its shorthands thereof.


T

-- 
Let's not fight disease by killing the patient. -- Sean 'Shaleh' Perry

"H. S. Teoh" <hsteoh@quickfur.ath.cx> wrote in message news:mailman.1957.1334898572.4860.digitalmars-d@puremagic.com...
>
> Good idea, I really need to work on my delegate syntax. I must admit I still have to look it up each time, 'cos I just can't remember the right syntax with all its shorthands thereof.
>

Heh, I can remember the shorthands: It's the full syntax (and syntax for referring to the type itself) that I can never remember. One puts "delegate" right next to the opening paren, the other puts something else there, meh, I can never keep that straight. But the shortcuts I always remember :)

On 4/20/12 1:09 PM, H. S. Teoh wrote:
> On Fri, Apr 20, 2012 at 08:44:06AM +0400, Denis Shelomovskij wrote:
>> 20.04.2012 8:06, H. S. Teoh написал:
>>> I'm writing some code that does some very simplistic parsing, and I'm
>>> just totally geeking out on how awesome D is for writing such code:
>>>
>>> 	import std.conv;
>>> 	import std.regex;
>>> 	import std.stdio;
>>>
>>> 	struct Data {
>>> 		string name;
>>> 		string phone;
>>> 		int age;
>>> 		... // a whole bunch of other stuff
>>> 	}
>>>
>>> 	void main() {
>>> 		Data d;
>>> 		foreach (line; stdin.byLine()) {
>>> 			auto m = match(line, "(\w+)\s+(\w+)");
>>
>> It's better not to create a regex every iteration. Use e.g.
>> ---
>> auto regEx = regex(`(\w+)\s+(\w+)`);
>> ---
>> before foreach. Of course, you are not claiming this as a
>> high-performance program, but creating a regex every iteration is
>> too common mistake to show such code to newbies.
>
> You're right, it was unoptimized code. I ended up using ctRegex for
> them:
>
> 	enum attrRx = ctRegex!`...`;
> 	enum blockRx = ctRegex!`...`;
>
> 	if (auto m = match(line, attrRx)) {
> 		...
> 	} else if (auto m = match(line, blockRx)) {
> 		...
> 	}
>
> The fact that D enums can be arbitrary types is just beyond awesome.

No, enum there means "manifest constant", it has nothing to do with an enumeration...

On Fri, Apr 20, 2012 at 04:25:30PM +0200, ixid wrote:
> As a D learner this thread is very interesting. It would be great to maintain it with a polished and error catching version that incorporates people's tweaks.

What I posted was a pared-down simplified version of the actual code I was working on. I've since done a few more iterations on it, and I thought I should perhaps post the entire code here as a complete example of a relatively simple but non-trivial D program that does something useful.


Some points of note in the code:

- I've factored out the code that does the AA lookups, because I found
  myself needing nested blocks in the input file. So the parseBlock()
  function does the real work, while the input file format is
  essentially specified by the loadSpec() function in the form of a
  nested AA structure containing delegates that implement parsing.  I
  think I like this much better than my original version; it's much more
  reusable, and arguably easier to read.

- Arguably, parseConds can be put into loadSpec() as well, but I'm
  anticipating needing to parse conditions from different places in the
  future, so it's a good idea to put encapsulate it as a separate
  function.

- Exceptions that occur during parsing are caught by code that iterates
  over lines, and exception messages are prefixed with the offending
  filename/line number. This is done in parseBlock(), and it can handle
  exceptions coming from anywhere (such as deeply nested inside one of
  the parsing delegates). Prefixed exceptions are translated into a
  different exception type, so that we don't prefix the same message
  more than once (parseBlock is called reentrantly by some of the
  delegates, so an exception occurring deep inside the call stack may
  traverse several instances of parseBlock during stack unwinding).

- I wrote a simple template for switching between regex() and ctRegex!()
  via a -version flag to the compiler. The regexes have also been
  hoisted out of inner loops, so that it doesn't introduce too much
  unnecessary overhead (besides, they're now compile-time evaluated so
  any such remaining overhead should be minimal). Gotta love D's CTFE
  capabilities!

- Another D coolness: finding the length of the longest name in a People
  array, in a single line of code:

	auto maxnamelen = reduce!"max(a,b.name.length)"(1, spec.people);

- To my great embarrassment, I didn't write any unittests. I should go
  to a corner and weep now.

- I'm sure that there's still lots of room for improvement; I'm by no
  means an expert in D. So criticisms, flames, fanmail, etc., are all
  welcome. ;-)


About the program itself:

The purpose of the program is to automatically assign M people out of a pool of N people to a recurring event on a rotating basis. For example, generate a toilet-scrubbing rotation schedule every Saturday for N roommates, or a guard duty schedule of 2 people each, etc..

While the basic problem is trivial, this program supports conditions and exclusive tags.

- Conditions basically indicate when a particular person is not
  available (e.g., person is away and won't be back till a certain date,
  person has conflicting event at that time, preplanned vacation,
  preplanned sickness, etc.).

- Exclusive tags basically say that two people having the same tag are
  not to be assigned to the same slot (e.g., they have personality
  conflicts and shouldn't be put together alone, or they're involved
  with another event that can only spare 1 person at a time, etc.).

- There's also a mixup parameter that lets you introduce some randomness
  into the rotation (for example, once in a while pair you up with a
  different person on guard duty, just for some variety).  This is to
  break the tedium of the same old people being assigned together all
  the time.

- Currently the output is just plain ole text. But it's not hard to add
  the capability of outputting, say, iCalendar format, HTML, XML, JSON,
  or whatever your favorite overhyped format is. All you need is to
  appropriately format the contents of the 'assigned' array and the date
  'dt' in genSched().


//----------------------------------snip---------------------------------
/**
 * Simple program to schedule assignments of N people to M slots on a
 * rotational basis.
 */

import std.algorithm;
import std.array;
import std.conv;
import std.datetime;
import std.random;
import std.regex;
import std.stdio;
import std.string;

//version = CtRgx;

template Re(string re) {
	version(CtRgx) {
		enum Re = ctRegex!re;
	} else {
		static Re = regex(re);
	}
}

struct ParseCtxt(R) {
	string fname;
	R      lines;
	int    linenum;
}

class ParseException : Exception {
	this(string msg) {
		super(msg);
	}
}

class Condition {
	abstract bool opCall(Date dt);
}

class SingleDateCond : Condition {
	Date dt;
	this(Date dt) { this.dt = dt; }
}

class DateRangeCond : Condition {
	Date start, end;
	this(Date start, Date end) {
		this.start = start;
		this.end = end;
	}
}

class NotCond : DateRangeCond {
	this(Date single_date) { super(single_date, single_date); }
	this(Date start, Date end) { super(start, end); }
	override bool opCall(Date dt) {
		return dt < this.start || dt > this.end;
	}
}

class AfterCond : SingleDateCond {
	this(Date dt) { super(dt); }
	override bool opCall(Date dt) {
		return dt > this.dt;
	}
}

struct Person {
	string name, phone, email;
	bool[string] tags;
	Condition[] conditions;

	bool eligible(Date dt) {
		foreach (cond; conditions) {
			if (!cond(dt))
				return false;
		}
		return true;
	}
}

struct SchedSpec {
	string   name;
	Date     startdate, enddate;
	Duration period;
	int      ppl_per_event;
	int      mixup;

	Person[] people;

	// People tagged with a tag in this list will not be scheduled together
	bool[string] excl_tags;

	bool[string] getExclTags(Person candidate) {
		bool[string] tags;
		foreach (tag; candidate.tags.keys) {
			if (!(tag in excl_tags))
				continue;

			tags[tag] = true;
		}

		return tags;
	}
}

alias void delegate(string key, string value) attrDg;
alias void delegate(string key) blockDg;

void parseBlock(R)(ref ParseCtxt!R ctxt, attrDg[string] attrDefs,
			blockDg[string] blockDefs=null)
{
	attrDg invalidAttr = delegate(string key, string value) {
		throw new Exception("Unknown attribute '%s'".format(key));
	};
	blockDg invalidBlock = delegate(string key) {
		throw new Exception("Unrecognized block '%s'".format(key));
	};

	auto blankLineRe = Re!`^\s*(#.*)?$`;
	auto attrRe  = Re!`^\s*(\w+)\s+(.*)$`;
	auto blockRe = Re!`^\s*(\w+)\s*:\s*$`;
	auto endRe   = Re!`^\s*end\s*$`;

	while (!ctxt.lines.empty) {
		auto line = ctxt.lines.front();
		ctxt.linenum++;

		debug writefln("[%d]>>%s$", ctxt.linenum, line);

		try {
			if (match(line, blankLineRe)) {
				ctxt.lines.popFront();
				continue;	// skip comments & empty lines
			} else if (auto m = match(line, attrRe)) {
				auto key = m.captures[1].idup;
				auto value = m.captures[2].idup;

				attrDefs.get(key, invalidAttr)(key, value);
			} else if (auto m = match(line, blockRe)) {
				auto key = m.captures[1].idup;

				ctxt.lines.popFront();
				blockDefs.get(key, invalidBlock)(key);
			} else if (match(line, endRe)) {
				return;
			} else {
				throw new Exception("Unrecognized spec: %s"
						.format(line));
			}
		} catch(ParseException e) {
			throw e;
		} catch(Exception e) {
			throw new ParseException("%s:%d: %s"
				.format(ctxt.fname, ctxt.linenum, e.msg));
		}

		ctxt.lines.popFront();
	}
}

Date parseDate(string dts) {
	auto dateRe = Re!`^\s*(\d{4})-(\d\d)-(\d\d)\s*$`;
	auto m = match(dts, dateRe);
	if (!m)
		throw new Exception("Invalid date '%s'".format(dts));

	return Date(to!int(m.captures[1]), to!int(m.captures[2]),
		to!int(m.captures[3]));
}

Date[2] parseDateRange(string str) {
	auto rangeRe = Re!`^\s*(\d+-\d+-\d+)(?:\s+to\s+(\d+-\d+-\d+))?`;
	auto m = match(str, rangeRe);
	if (!m)
		throw new Exception("Invalid date range '%s'".format(str));

	auto start = parseDate(m.captures[1]);
	auto end = (m.captures.length >= 2 && m.captures[2].length > 0) ?
			parseDate(m.captures[2]) : start;

	return [start, end];
}

Duration parseDur(string durs) {
	auto daysRe = Re!`^\s*(\d+)\s*days\s*$`;
	auto weeksRe = Re!`^\s*(\d+)\s*weeks\s*$`;

	if (auto m = match(durs, daysRe)) {
		return dur!"days"(to!int(m.captures[1]));
	} else if (auto m = match(durs, weeksRe)) {
		return dur!"weeks"(to!int(m.captures[1]));
	}

	throw new Exception("Unrecognized duration '%s'".format(durs));
}

void parseConds(C)(ref C ctxt, ref Condition[] conds) {
	parseBlock(ctxt, [
		"after": (string key, string value) {
			conds ~= new AfterCond(parseDate(value));
		},
		"not": (string key, string value) {
			auto range = parseDateRange(value);
			conds ~= new NotCond(range[0], range[1]);
		}
	]);
}

SchedSpec loadSpec(string fname) {
	auto specfile = File(fname, "r");
	scope(exit) specfile.close();

	alias typeof(specfile.byLine()) L;
	auto ctxt = ParseCtxt!L(fname, specfile.byLine());

	SchedSpec spec;

	parseBlock(ctxt, [
		"name": (string key, string value) {
			spec.name = value.idup;
		},
		"startdate": (string key, string value) {
			spec.startdate = parseDate(value);
		},
		"enddate": (string key, string value) {
			spec.enddate = parseDate(value);
		},
		"period": (string key, string value) {
			spec.period = parseDur(value);
		},
		"ppl_per_event": (string key, string value) {
			spec.ppl_per_event = to!int(value);
		},
		"mixup": (string key, string value) {
			spec.mixup = to!int(value);
		},
		"exclusive_tags": (string key, string value) {
			foreach (tag; splitter(value, Re!`\s+`)) {
				spec.excl_tags[tag] = true;
			}
		}
	], [
		"person": (string key) {
			Person person;

			parseBlock(ctxt, [
				"name": (string key, string value) {
					person.name = value;
				},
				"phone": (string key, string value) {
					person.phone = value;
				},
				"email": (string key, string value) {
					person.email = value;
				},
				"tags": (string key, string value) {
					foreach (tag; splitter(value,
							Re!`\s+`))
					{
						person.tags[tag] = true;
					}
				}
			], [
				"conditions": (string key) {
					parseConds(ctxt, person.conditions);
				}
			]);

			spec.people ~= person;
		}
	]);

	return spec;
}

void summarize(SchedSpec spec) {
	writefln("Specification '%s':", spec.name);
	writefln("\tStart date: %s", spec.startdate);
	writefln("\tEnd date:   %s", spec.enddate);
	writefln("\tRepeat period:    %s", spec.period);
	writefln("\tPeople per event: %d", spec.ppl_per_event);
	writefln("\tTotal people:     %d", spec.people.length);
}

enum string[] monthAbbrev = [
	"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct",
	"Nov", "Dec"
];

void genSched(SchedSpec spec) {
	//summarize(spec);

	Person[] queue = spec.people[0..$];
	randomShuffle(queue);

	auto maxnamelen = reduce!"max(a,b.name.length)"(1, spec.people);

	Date dt = spec.startdate;
	while (dt <= spec.enddate) {
		Person[] assigned;
		bool[string] excl_tags;

		foreach (i; 0 .. spec.ppl_per_event) {
			// Find eligible person for assignment
			bool eligible(Person p, Date dt) {
				if (!p.eligible(dt))
					return false;

				// Check for exclusive tag conflicts
				auto ptags = spec.getExclTags(p);
				foreach (tag; ptags.byKey()) {
					if (tag in excl_tags)
						return false;
				}
				return true;
			}
			auto j = countUntil!eligible(queue, dt);

			if (j == -1)
				throw new Exception("No eligible assignees "~
						"found on %s!".format(dt));

			// Move person into assigned list
			assigned ~= queue[j];
			replaceInPlace(queue, j, j+1, cast(Person[])[]);

			// Add person's exclusive tags to the current set of
			// exclusive tags.
			foreach (tag; spec.getExclTags(assigned[$-1]).byKey())
			{
				excl_tags[tag] = true;
			}
		}

		// Put assigned people back to the end of the queue, but with a
		// probability of permuting the order so that we get a mix of
		// different groupings every now and then.
		foreach (p; assigned) {
			insertInPlace(queue, queue.length -
					uniform(0, spec.mixup+1), [p]);
		}

		writef("%04d %s %2d:", dt.year, monthAbbrev[dt.month-1], dt.day);
		foreach (p; assigned) {
			writef("\t%-*s", maxnamelen, p.name);
		}
		writeln();

		dt += spec.period;
	}
}

int showhelp(string progname) {
	writefln("Usage: %s [inputfile]", progname);
	return 1;
}

int main(string[] args) {
	assert(args.length >= 1);
	try {
		if (args.length <= 1)
			return showhelp(args[0]);

		auto inputfile = args[1];
		auto spec = loadSpec(inputfile);
		genSched(spec);
	} catch(Exception e) {
		writefln("Error: %s", e.msg);
	}

	return 0;
}
//----------------------------------snip---------------------------------


T

-- 
Guns don't kill people. Bullets do.

I can't compile it. I get "Out of memory". Is it the regex.d module again ?:(
This one really needs to be fixed ASAP, as the older working regexp is deprecated.

On 21.04.2012 11:46, SomeDude wrote:
> I can't compile it. I get "Out of memory". Is it the regex.d module
> again ?:(
> This one really needs to be fixed ASAP, as the older working

Ah-ha-ha. OK, come on use it the source are out there in the open :)
It didn't even handle * properly.

 regexp is
> deprecated.

Just stop using ctRegex for now... it's experimental.

Or more to the point the problem is this. I've seen this one on bugzilla:

version(CtRgx) {
		enum Re = ctRegex!re;//auto is OK here BTW
	} else {//that's the problem. It's _parsed_ at compile-time
		static Re = regex(re);//switch static to auto
	}
}

And there is little I can do untill CTFE stops bleeding RAM.

-- 
Dmitry Olshansky

On Saturday, 21 April 2012 at 10:21:49 UTC, Dmitry Olshansky wrote:
> Just stop using ctRegex for now... it's experimental.
>
> Or more to the point the problem is this. I've seen this one on bugzilla:
>
> version(CtRgx) {
> 		enum Re = ctRegex!re;//auto is OK here BTW
> 	} else {//that's the problem. It's _parsed_ at compile-time
> 		static Re = regex(re);//switch static to auto
> 	}
> }
>
> And there is little I can do untill CTFE stops bleeding RAM.

Well, neither of those works:

 version(CtRgx) {
 	   auto Re = ctRegex!re;//auto is OK here BTW
 	} else {//that's the problem. It's _parsed_ at compile-time
 	   auto Re = regex(re);//switch static to auto
 	}

On 21.04.2012 14:48, SomeDude wrote:
> On Saturday, 21 April 2012 at 10:21:49 UTC, Dmitry Olshansky wrote:
>> Just stop using ctRegex for now... it's experimental.
>>
>> Or more to the point the problem is this. I've seen this one on bugzilla:
>>
>> version(CtRgx) {
>> enum Re = ctRegex!re;//auto is OK here BTW
>> } else {//that's the problem. It's _parsed_ at compile-time
>> static Re = regex(re);//switch static to auto
>> }
>> }
>>
>> And there is little I can do untill CTFE stops bleeding RAM.
>
> Well, neither of those works:
>
> version(CtRgx) {
> auto Re = ctRegex!re;//auto is OK here BTW
> } else {//that's the problem. It's _parsed_ at compile-time
> auto Re = regex(re);//switch static to auto
> }
>
>

Probably there are other cases where compiler const folds stuff I dunno.

-- 
Dmitry Olshansky

On Sat, Apr 21, 2012 at 03:12:05PM +0400, Dmitry Olshansky wrote:
> On 21.04.2012 14:48, SomeDude wrote:
> >On Saturday, 21 April 2012 at 10:21:49 UTC, Dmitry Olshansky wrote:
> >>Just stop using ctRegex for now... it's experimental.
> >>
> >>Or more to the point the problem is this. I've seen this one on bugzilla:
> >>
> >>version(CtRgx) {
> >>enum Re = ctRegex!re;//auto is OK here BTW
> >>} else {//that's the problem. It's _parsed_ at compile-time
> >>static Re = regex(re);//switch static to auto
> >>}
> >>}
> >>
> >>And there is little I can do untill CTFE stops bleeding RAM.
> >
> >Well, neither of those works:
> >
> >version(CtRgx) {
> >auto Re = ctRegex!re;//auto is OK here BTW
> >} else {//that's the problem. It's _parsed_ at compile-time
> >auto Re = regex(re);//switch static to auto
> >}
[...]

Hmph. I should've checked dmd memory usage when I wrote that. :-(

But anyway, even on my souped up AMD hexacore system, the ctRegex version takes significantly longer to compile than the non-ctRegex version. Perhaps I should just avoid ctRegex for now (though it *is* an ultracool feature of std.regex).

I'm getting confused about the use of 'static' in this context. What I wanted was to make the regex module-global, but apparently 'static' has an overloaded meaning here, and also makes it compile-time evaluated? How do I make it module-global without being compile-time evaluated??


T

-- 
"You know, maybe we don't *need* enemies." "Yeah, best friends are about all I can take." -- Calvin & Hobbes

On 21.04.2012 18:41, H. S. Teoh wrote:
[snip]
> How do I make it module-global without being compile-time evaluated??
>
>

No idea ;)

But as a workaround:

Global blah;

static this(){
	blah = ...;
}

-- 
Dmitry Olshansky