--- a/dynamin/painting/text_layout.d	Tue May 01 21:53:58 2012 -0500
+++ b/dynamin/painting/text_layout.d	Wed May 02 03:19:00 2012 -0500
@@ -15,7 +15,7 @@
  * The Original Code is the Dynamin library.
  *
  * The Initial Developer of the Original Code is Jordan Miner.
- * Portions created by the Initial Developer are Copyright (C) 2007-2010
+ * Portions created by the Initial Developer are Copyright (C) 2007-2012
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
@@ -25,12 +25,16 @@
 
 module dynamin.painting.text_layout;
 
+import dynamin.painting_backend;
 import dynamin.core.list;
 import dynamin.core.string;
 import dynamin.painting.color;
+import dynamin.painting.coordinates;
 import tango.text.convert.Utf;
 import tango.io.Stdout;
 
+//version = TextLayoutDebug;
+
 //{{{ character formatting types
 /// The line style of an underline, strikethrough, or overline.
 // TODO: add images of what these line styles look like
@@ -44,9 +48,9 @@
 	///
 	Dotted,
 	///
-	Dashed,
+	//Dashed,
 	///
-	Wavy
+	//Wavy
 }
 
 ///
@@ -219,7 +223,10 @@
 	///
 	Right,
 	///
-	Justify
+	/// The last line of justified text will be natural aligned.
+	Justify,
+	/// Left aligned for left-to-right text and right aligned for right-to-left text.
+	Natural
 }
 
 ///
@@ -244,10 +251,58 @@
 	char leading = '.';
 }
 
+struct Run {
+	cairo_scaled_font_t* font;
+	float baseline;    // distance from position.y down to the baseline
+	float height;
+	Point position;    // the top-left corner of the run
+	uint start;        // the first UTF-8 code unit in this run
+	uint length;       // the number of UTF-8 code units in this run
+	bool rightToLeft;
+	uint[] clusterMap; // map from UTF-8 code units to the beginning of the glyph cluster they're in
+	uint[] glyphs;     // glyphs are in visual order
+	float[] advanceWidths;
+
+	uint end() { return start + length; }
+	float width() {
+		float sum = 0;
+		foreach(w; advanceWidths)
+			sum += w;
+		return sum;
+	}
+}
+struct LogAttr {
+	private ubyte data;
+	// true if the line can be broken at this index
+	bool softBreak() {
+		return cast(bool)(data & 1);
+	}
+	void softBreak(bool b) {
+		b ? (data |= 1) : (data &= ~1);
+	}
+	// true if the caret can be placed at this index
+	bool clusterStart() {
+		return cast(bool)(data & 2);
+	}
+	void clusterStart(bool b) {
+		b ? (data |= 2) : (data &= ~2);
+	}
+	// true if the caret can be placed at this index when moving to the beginning of a word
+	bool wordStart() {
+		return cast(bool)(data & 4);
+	}
+	void wordStart(bool b) {
+		b ? (data |= 4) : (data &= ~4);
+	}
+}
 /**
- *
+ * Normally, at least for situations when paragraphs need to be formatted differently (e.g. one
+ * centered and another justified), a separate TextLayout object is used for each paragraph.
  */
 class TextLayout {
+private:
+	mixin TextLayoutBackend;
+public:
 	string text;
 	Rect[] layoutBoxes;
 	///
@@ -261,24 +316,96 @@
 	double lineSpacing = 1.0;
 	double defaultTabStopLocations = 0; // 0 means default tabs every (4 * width of character '0')
 	TabStop[] tabStops;
-	TextAlignment alignment = TextAlignment.Left;
+	TextAlignment alignment = TextAlignment.Natural;
 
+	List!(Run) runs; // runs are in logical order
+	LogAttr[] logAttrs;
+	void clearRuns() {
+		while(runs.count > 0)
+			releaseScaledFont(runs.pop().font);
+	}
 	void defaultGetLineBoxes(Rect line, List!(Rect) boxes) {
 		boxes.add(line);
 	}
 	this(string fontFamily, double fontSize) {
 		getLineBoxes = &defaultGetLineBoxes;
+		runs = new List!(Run);
+		if(!runLists)
+			runLists = new List!(List!(Run));
+		runLists.add(runs); // to keep the runs list around until the destructor is called
+
 		formatting = new List!(FormatChange);
 		initialFormat.fontFamily = fontFamily;
 		initialFormat.fontSize = fontSize;
 	}
-	invariant {
+	~this() {
+		clearRuns(); // have to call releaseScaledFont() so unused ones don't stay in font cache
+		runLists.remove(runs);
+	}
+	/*invariant { // TODO: uncomment this when D no longer calls it right before the destructor
 		// ensure that formatting is sorted correctly
 		uint index = 0;
 		foreach(change; formatting) {
 			assert(change.index >= index);
 			index = change.index;
 		}
+	}*/
+	// The first number is the index of the run to put at the left of the first line.
+	// The second number is the index of the run to put just right of that, and so on.
+	uint[] visToLogMap;  // length == runs.count
+	// Narrow down the visual to logical map to just the logical runs between startRun and endRun.
+	// startRun is inclusive; endRun is exclusive
+	// The first number in the return map is index of the run (between startRun and
+	// endRun) that goes first visually. The second index goes just to right of it, and so on.
+	void getVisualToLogicalMap(uint startRun, uint endRun, uint[] map) {
+		assert(map.length == endRun - startRun);
+		uint mapIndex = 0;
+		for(int i = 0; i < visToLogMap.length; ++i) {
+			// we are basically removing all numbers from visToLogMap except ones >= start and < end
+			if(visToLogMap[i] >= startRun && visToLogMap[i] < endRun) {
+				map[mapIndex] = visToLogMap[i];
+				mapIndex++;
+			}
+		}
+		assert(mapIndex == map.length - 1);
+
+		// To use a logical to visual map to implement this function, you'd have to
+		// loop through the entire map and find the smallest index. Then put that in the
+		// return array. Then loop through and find the second smallest index, and put that in
+		// the return array. Repeat until it is filled.
+	}
+	// Splits this run into two runs. This Run is the second one, and the first run is returned.
+	void splitRun(uint runIndex, uint splitIndex) {
+		// TODO: need to update visToLogMap
+		// TODO: rename position to location?
+		version(TextLayoutDebug) {
+			Stdout.format("splitRun(): runIndex: {0}, text: {1}",
+			              runIndex, text[runs[runIndex].start..runs[runIndex].end]).newline;
+		}
+		assert(splitIndex != runs[runIndex].start && splitIndex != runs[runIndex].end);
+		assert(logAttrs[splitIndex].clusterStart);
+
+		runs.insert(runs[runIndex], runIndex);
+
+		Run* run1 = &runs.data[runIndex];
+		auto glyphIndex = run1.clusterMap[splitIndex - run1.start];
+		run1.length        = splitIndex - run1.start;
+		run1.glyphs        = run1.glyphs[0..glyphIndex];
+		run1.advanceWidths = run1.advanceWidths[0..glyphIndex];
+		run1.clusterMap    = run1.clusterMap[0..run1.length];
+		cairo_scaled_font_reference(run1.font);
+
+		Run* run2 = &runs.data[runIndex+1];
+		run2.length        = (run2.start + run2.length) - splitIndex;
+		run2.start         = splitIndex;
+		run2.glyphs        = run2.glyphs[glyphIndex..$];
+		run2.advanceWidths = run2.advanceWidths[glyphIndex..$];
+		run2.clusterMap    = run2.clusterMap[run1.length..$];
+		// need to change the cluster map to account for the glyphs removed
+		for(int i = 0; i < run2.clusterMap.length; ++i)
+			run2.clusterMap[i] -= glyphIndex;
+
+		backend_splitRun(runIndex, splitIndex);
 	}
 
 	///
@@ -377,6 +504,37 @@
 		return iter;
 	}
 
+	/**
+	 *
+	 */
+	TextAlignment naturalAlignment() {
+		return TextAlignment.Left; // TODO:
+	}
+	/**
+	 *
+	 */
+	TextAlignment resolvedAlignment() {
+		if(alignment == TextAlignment.Left || alignment == TextAlignment.Right)
+			return alignment;
+		else
+			return naturalAlignment;
+	}
+
+	/*
+	Point indexToPoint(uint index) {
+	}
+	uint pointToIndex(Point pt) {
+	}
+	uint nextLeft(uint index) {
+	}
+	uint nextRight(uint index) {
+	}
+	uint nextWordLeft(uint index) {
+	}
+	uint nextWordRight(uint index) {
+	}
+	*/
+
 	//{{{ character formatting
 	void setFontFamily(string family, uint start, uint length) {
 		FormatData data;
@@ -489,14 +647,562 @@
 		formatting.insert(change, i);
 	}
 	//}}}
+
 	private void checkIndex(uint index) {
 		if(index == 0)
 			return;
-		if(cropRight!(char)(text[0..index]).length != index)
+		// NOTE: Do not use cropRight(). It is broken. It will cut off an ending code point even
+		// when it is a perfectly valid string. Thankfully, cropLeft() works.
+		if(cropLeft!(char)(text[index..$]).length != text.length-index)
 			throw new Exception("index must be at a valid code point, not inside one");
 	}
+
+	protected void layout(Graphics g) {
+		backend_preprocess(g);
+
+		version(TextLayoutDebug)
+			Stdout("-----layout start-----").newline;
+		int lastRunIndex = 0; // used in case of a bug
+		LayoutProgress progress;
+		lineLoop:
+		// loop once for each line until done laying out text
+		while(progress.runIndex < runs.count) {
+			// Try laying out the line at the height of the first run.
+			// If a taller run is found, try the line at that height, and so on
+			// If no taller run is found, or if laying out the line at the taller height didn't
+			// fit more characters on, then we've found the height that works best.
+			double baseline;
+			double height = 0;    // height of the line
+			uint prevLength = 0;  // how many chars fit on when the line is that tall
+			double heightToTry = runs[progress.runIndex].height;
+			while(true) {
+				baseline = 0;
+				double newHeightToTry = heightToTry;
+				uint length = layoutLine(newHeightToTry, baseline, progress, true);
+				if(length == 0) { // we ran out of layout boxes--no place to put text
+					while(runs.count > progress.runIndex)
+						runs.removeAt(runs.count-1);
+					break lineLoop;
+				}
+				version(TextLayoutDebug)
+					Stdout.format("^ length: {0}, runIndex: {1}, y: {2}", length, progress.runIndex, progress.y).newline;
+				if(length > prevLength) { // if more fit on at heightToTry than height
+					height = heightToTry;
+					prevLength = length;
+					if(newHeightToTry <= heightToTry) // if no need to try again
+						break;
+					heightToTry = newHeightToTry;
+				} else {
+					break;
+				}
+			}
+			// now that we have found the right height and baseline for the line,
+			// actually do the layout
+			layoutLine(height, baseline, progress, false);
+
+			version(TextLayoutDebug) {
+				Stdout.format("^^ rI: {0}, y: {1}", progress.runIndex, progress.y).newline;
+				if(runIndex == lastRunIndex)
+					Stdout("assert failed").newline;
+			}
+			assert(progress.runIndex > lastRunIndex);
+			// should never happen, but if there is a bug, it is better than an infinite loop
+			if(progress.runIndex == lastRunIndex)
+				break;
+			lastRunIndex = progress.runIndex;
+		}
+		// if wrapping around an object, a tab should go on the other side of the object
+	}
+
+	struct LayoutProgress {
+		int runIndex = 0;
+		int boxIndex = 0;
+		double y = 0;     // y is relative to the top of the layout box
+	}
+
+	// {{{ layoutLine()
+	// Returns how many chars fit on the line when it is the specified height tall.
+	// When this method returns, height will have been set to a new height that layoutLine() can
+	// be called with.
+	// runIndex and totalY are only updated if dryRun is false
+	// totalY is the total height of text layed out before this
+	// note that this includes empty space at the bottom of a layout box where a line couldn't fit
+	List!(Rect) lineBoxes; // try to reuse the same memory for each call
+	uint layoutLine(ref double height, ref double baseline,
+	                 ref LayoutProgress progress, bool dryRun) {
+		// make local copies in case of dryRun
+		int boxIndex = progress.boxIndex;
+		double y = progress.y; // for now, y is relative to the top of the layout box
+		// if the line won't fit on, go to the top of the next box
+		while(y + height > layoutBoxes[boxIndex].height) {
+			boxIndex++;
+			if(boxIndex == layoutBoxes.length)
+				return 0;
+			y = 0;
+		}
+		Rect layoutBox = layoutBoxes[boxIndex];
+		if(!dryRun) {
+			progress.boxIndex = boxIndex;
+			progress.y = y + height; // top of line after this one
+		}
+		// change y to absolute
+		y += layoutBox.y;
+
+		/*
+		double top = totalY; // top will be the space from layoutBox.y to the top of the line
+		foreach(i, box; layoutBoxes) {
+			layoutBox = box; // use the last box if we never break
+			if(top >= box.height) {
+				top -= box.height;
+				if(i == layoutBoxes.length - 1)
+					return 0; // if we are out of layout boxes, there is no place to put text
+			} else if(top + height > box.height) {
+				// add on empty space at bottom of box
+				totalY += dryRun ? 0 : top + height - box.height;
+				top = 0; // loop to next box, then break
+				if(i == layoutBoxes.length - 1)
+					return 0; // if we are out of layout boxes, there is no place to put text
+			} else {
+				break;
+			}
+		}
+		totalY += dryRun ? 0 : height;*/
+
+		if(!lineBoxes)
+			lineBoxes = new List!(Rect);
+		lineBoxes.clear();
+		getLineBoxes(Rect(layoutBox.x, y, layoutBox.width, height), lineBoxes);
+
+
+		version(TextLayoutDebug) {
+			Stdout.format("layoutLine(): height: {0}, runIndex: {1}, dryRun: {2}, runs[rI]: {3}",
+			              height, runIndex, dryRun,
+			              text[runs[runIndex].start..runs[runIndex].end]).newline;
+		}
+		int totalWidth = 0;
+		foreach(box; lineBoxes)
+			totalWidth += box.width;
+		wordsLoop:
+		for(int words = getMaxWords(progress.runIndex, totalWidth); words >= 1; --words) {
+			// then for right-aligned, start with the last line box and last run, and work left
+			// for left-aligned, start with the first line box and first run, and work right
+
+			// loop over each glyph/char from left to right
+			//
+			int endRun, runSplit;
+			getRuns(words, progress.runIndex, endRun, runSplit);
+			version(TextLayoutDebug) {
+				Stdout.format("    words: {0}, endRun: {1}, runSplit: {2}",
+				              words, endRun, runSplit).newline;
+			}
+			assert(runSplit > 0);
+
+			GlyphIter lastSoftBreak;
+			GlyphIter iter;
+			iter.runs = runs;
+			iter.startRun = progress.runIndex;
+			iter.endRun = endRun;
+			iter.endSplit = runSplit;
+			lastSoftBreak = iter;
+
+			int boxI = 0;
+
+			int lastRunIndex = iter.runIndex;
+			cairo_font_extents_t lastRunExtents;
+			lastRunExtents.ascent = lastRunExtents.descent = lastRunExtents.height = 0;
+
+			float x = lineBoxes[0].x;
+			while(iter.next()) {
+				if(iter.runIndex != lastRunIndex) {
+					// If this isn't a dry run, blindly trust the height and baseline.
+					// nothing we could do if they were wrong
+					if(!dryRun) {
+						iter.run.position = Point(x, y);
+						iter.run.baseline = baseline;
+					} else {
+						// if this new run is taller, return the taller height and baseline
+						cairo_font_extents_t extents;
+						cairo_scaled_font_extents(iter.run.font, &extents);
+						auto below = max(extents.height-extents.ascent,
+										 lastRunExtents.height-lastRunExtents.ascent);
+						baseline = max(baseline, extents.ascent, lastRunExtents.ascent);
+						// floats aren't exact, so require a tenth of a pixel higher
+						if(baseline + below > height + 0.1) {
+							height = baseline + below;
+							return iter.charCount;
+						}
+						lastRunExtents = extents;
+					}
+				}
+				lastRunIndex = iter.runIndex;
+
+				if(logAttrs[iter.charIndex+iter.run.start].softBreak)
+					lastSoftBreak = iter;
+
+				x += iter.advanceWidth;
+				// we always have to put at least one word per line
+				if(x > lineBoxes[boxI].right && words > 1) {
+					version(TextLayoutDebug)
+						Stdout.format("    hit end of line box, boxI: {0}", boxI).newline;
+					boxI++;
+					if(boxI == lineBoxes.count)  // we failed at getting all the text on
+						continue wordsLoop;      // try again with one fewer word
+					x = lineBoxes[boxI].x;
+
+					if(!dryRun) {
+						splitRun(lastSoftBreak.runIndex, lastSoftBreak.charIndex+lastSoftBreak.run.start);
+						lastSoftBreak.endRun += 1;
+					}
+					iter = lastSoftBreak;
+				}
+				// if LTR, loop over clusterMap and logAttrs forward; if RTL, loop reverse
+			}
+			// getting to here means that we were successful in getting the text on
+
+
+			if(!dryRun) {
+				if(runSplit != 0 && runSplit != runs[iter.endRun-1].length) {
+					splitRun(iter.endRun-1, runSplit+runs[iter.endRun-1].start);
+				}
+				// now that we know for sure what runs are on the line, set their height
+				for(int i = progress.runIndex; i < iter.endRun; ++i)
+					runs.data[i].height = height;
+				progress.runIndex = iter.endRun;
+			}
+			return iter.charCount;
+
+			/*if(resolvedAlignment == TextAlignment.Left) {
+			} else if(resolvedAlignment == TextAlignment.Right) {
+			} else {
+				assert(false);
+			}*/
+		}
+		assert(false, "reached end of layoutLine()");
+	}
+	// }}}
+
+	// {{{ getMaxWords()
+	// returns the maximum number of words, starting at runIndex, that could fit in
+	// the specified width
+	int getMaxWords(int runIndex, float width) {
+		int start = runs[runIndex].start;
+
+		// find out how many glyphs will fit in the width
+		int glyphIndex;
+		both:
+		for(; runIndex < runs.count; ++runIndex) {
+			// have to go over runs and glyphs in logical order because all the characters on
+			// the first line are logically before all the runs on the second line, and so on.
+			glyphIndex = runs[runIndex].rightToLeft ? runs[runIndex].glyphs.length-1 : 0;
+			while(glyphIndex >= 0 && glyphIndex < runs[runIndex].glyphs.length) {
+				width -= runs[runIndex].advanceWidths[glyphIndex];
+				if(width < 0)
+					break both;
+				glyphIndex += runs[runIndex].rightToLeft ? -1 : 1;
+			}
+		}
+		if(runIndex == runs.count)
+			runIndex--;
+
+		// find which character goes with the last glyph
+		int charIndex = 0;
+		while(charIndex < runs[runIndex].length) {
+			if(runs[runIndex].rightToLeft && runs[runIndex].clusterMap[charIndex] < glyphIndex)
+				break;
+			if(!runs[runIndex].rightToLeft && runs[runIndex].clusterMap[charIndex] > glyphIndex)
+				break;
+			charIndex++;
+		}
+		int end = charIndex + runs[runIndex].start;
+
+		// find out how many words are in the character range (and thus in the glyphs)
+		int words = 0;
+		for(int i = start; i < end; ++i) {
+			if(logAttrs[i].softBreak)
+				words++;
+		}
+		if(end == text.length || words == 0) // consider the end as the start of another word
+			words++;
+		return words;
+	}
+	// }}}
+
+	// {{{ struct GlyphIter
+	// TODO: need to loop using visualToLogicalOrder
+	struct GlyphIter {
+		List!(Run) runs;
+		void startRun(int index) { runIndex = index - 1; }
+		int endRun;
+		int endGlyphSplit; // the number of glyphs in the last run
+		// sets the number of characters in the last run
+		void endSplit(int split) {
+			assert(split <= runs[endRun-1].length);
+			if(split == runs[endRun-1].length)
+				endGlyphSplit = runs[endRun-1].glyphs.length;
+			else
+				endGlyphSplit = runs[endRun-1].clusterMap[split];
+		}
+
+		int runIndex = -1;
+		// usually the character that produced the current glyph (except when reordered)
+		int charIndex = 0;  // counting from the start of the run
+		int glyphIndex = -1;
+		int charCount = 1; // charIndex starts at 0; it has already advanced to the first char
+
+		Run* run() { return &runs.data[runIndex]; }
+
+		// need to call once before getting the first glyph
+		// returns true if there is another valid glyph to use
+		// if false is returned, do not access any more glyphs or call next() again
+		bool next() {
+			assert(runIndex < endRun);
+			//Stdout("glyphIndex: ")(glyphIndex)("  runIndex: ")(runIndex).newline;
+
+			if(glyphIndex == -1 || glyphIndex == runs[runIndex].glyphs.length-1) {
+				runIndex++;
+				if(runIndex == endRun)
+					return false;
+				glyphIndex = 0;
+				charCount += run.rightToLeft ? charIndex : run.length-charIndex;
+				charIndex = run.rightToLeft ? run.length-1 : 0;
+				if(runIndex == endRun-1 && runs[runIndex].rightToLeft)
+					glyphIndex = endGlyphSplit-1;
+			} else {
+				glyphIndex++;
+			}
+			if(runIndex == endRun-1) {
+				if(!runs[runIndex].rightToLeft && glyphIndex == endGlyphSplit)
+					return false;
+				if(runs[runIndex].rightToLeft && glyphIndex == runs[runIndex].glyphs.length)
+					return false;
+			}
+
+			// advance charIndex, if needed
+			auto newChar = charIndex;
+			while(newChar >= 0 && newChar < run.length) {
+				// if we found the next cluster
+				if(run.clusterMap[newChar] != run.clusterMap[charIndex]) {
+					// if the next char produced a glyph after where we are, then stay put
+					if(run.clusterMap[newChar] > glyphIndex)
+						break;
+					charCount += newChar-charIndex > 0 ? newChar-charIndex : charIndex-newChar;
+					charIndex = newChar;
+				}
+				newChar += run.rightToLeft ? -1 : 1;
+			}
+
+			//Stdout("  *glyphIndex: ")(glyphIndex)("  runIndex: ")(runIndex).newline;
+			return true;
+		}
+		float advanceWidth() { return runs[runIndex].advanceWidths[glyphIndex]; }
+	}
+	// }}}
+
+	// words is the number of words the runs should contain
+	// startRun is the index of the first run to count words for
+	// endRun is the index of the last run plus 1 (the last run exclusive)
+	// endRunSplit is how many characters in the last run it takes to get the specified word count
+	void getRuns(int words, int startRun, out int lastRun, out int lastRunSplit) {
+		assert(words >= 1);  // TODO: change endRun to lastRun and make it inclusive
+		lastRun = startRun;
+		// add 1 to start with so that if a run begins with a word, it doesn't count
+		for(int i = runs[startRun].start + 1; i < text.length; ++i) {
+			if(runs[lastRun].end < i)
+				lastRun++;
+			if(logAttrs[i].softBreak) {
+				words--;
+				if(words == 0) {
+					lastRunSplit = i - runs[lastRun].start;
+					lastRun++; // TODO: hack
+					return;
+				}
+			}
+		}
+		lastRun = runs.count - 1;
+		lastRunSplit = runs[lastRun].length;
+		lastRun++; //hack
+	}
+
+	// {{{ draw()
+	// TODO: make layout() protected
+	// functions should call it automatically when needed
+	List!(cairo_glyph_t) glyphs;
+	void draw(Graphics g) { // TODO: take a layoutBoxIndex parameter to only draw one of them?
+		layout(g); // TODO: fix to only call if needed
+
+		if(!glyphs)
+			glyphs = new List!(cairo_glyph_t)(80);
+
+		/*
+		 * If runs are removed because not all the text will fit in the layout boxes,
+		 * then we need to split at the end of the last one in splitter(), and break out
+		 * of the loop when we reach the last run, since otherwise it goes to the end of
+		 * the text.
+		 */
+		int splitter(uint i) {
+			return i < runs.count ? runs[i].start : (i == runs.count ? runs[runs.count-1].end : -1);
+		}
+		int runIndex = 0;
+		double x = runs[runIndex].position.x;
+		foreach(start, length, format; formatRuns(&splitter)) {
+			uint end = start + length;
+
+			if(runs[runIndex].end == start) {
+				runIndex++;
+				if(runIndex == runs.count) // happens if runs were removed because they didn't fit
+					break;
+				x = runs[runIndex].position.x;
+				if(runs[runIndex].rightToLeft)
+					x += runs[runIndex].width;
+			}
+			Run* r = &runs[runIndex];
+			assert(r.end >= end);
+
+			cairo_matrix_t ctm;
+			cairo_get_matrix(g.handle, &ctm);
+			double x0 = ctm.x0, y0 = ctm.y0;
+			cairo_scaled_font_get_ctm(r.font, &ctm);
+			ctm.x0 = x0, ctm.y0 = y0;
+			cairo_set_matrix(g.handle, &ctm);
+			cairo_set_scaled_font(g.handle, r.font);
+
+			//Stdout(r.position)("  ")(text[start..end]).newline;
+			// note: using 'length' in a slice doesn't mean the 'length' in scope--it means the
+			// length of the array you are slicing...arg, wasted 15 minutes
+
+			// find glyphs to draw
+			int glyphStart;
+			int glyphEnd;
+			// TODO: I believe this setting glyphStart/End works right, but can it be shortened?
+			// besides the places the index equals the length, could just swap gStart and gEnd?
+			if(r.rightToLeft) {
+				if(start-r.start == 0)
+					glyphEnd = r.glyphs.length;
+				else
+					glyphEnd = r.clusterMap[start-r.start];
+				if(end-r.start == r.clusterMap.length)
+					glyphStart = 0;
+				else
+					glyphStart = r.clusterMap[end-r.start];
+			} else {
+				glyphStart = r.clusterMap[start-r.start];
+				if(end-r.start == r.clusterMap.length)
+					glyphEnd = r.glyphs.length;
+				else
+					glyphEnd = r.clusterMap[end-r.start];
+			}
+			//if(r.rightToLeft)
+			//	Stdout(glyphStart)(" -- ")(glyphEnd).newline;
+
+			// draw backColor
+			float width = 0;
+			for(int i = glyphStart; i < glyphEnd; ++i)
+				width += r.advanceWidths[i];
+			Rect rect = Rect(r.rightToLeft ? x-width : x, r.position.y, width, r.height);
+			g.source = format.backColor;
+			g.rectangle(rect);
+			g.fill();
+
+			// draw glyphs
+			int j = r.rightToLeft ? glyphEnd-1 : glyphStart;
+			while(j >= glyphStart && j < glyphEnd) {
+				if(r.rightToLeft)
+					x -= r.advanceWidths[j];
+				cairo_glyph_t cairoGlyph;
+				cairoGlyph.index = r.glyphs[j];
+				cairoGlyph.x = x;
+				cairoGlyph.y = r.position.y + r.baseline;
+				//Stdout.format("x {0} y {1}", cairoGlyph.x, cairoGlyph.y).newline;
+				glyphs.add(cairoGlyph);
+				if(!r.rightToLeft)
+					x += r.advanceWidths[j];
+				r.rightToLeft ? j-- : j++;
+			}
+			//Stdout.format("start {0}, color: {1}", start, format.foreColor.B).newline;
+			g.source = format.foreColor;
+			cairo_show_glyphs(g.handle, glyphs.data.ptr, glyphs.count);
+			glyphs.clear();
+		}
+	}
+	// }}}
+
+private:
+	// {{{ font cache
+	// Returns a scaled font matching the specified look. If the font is in the font cache
+	// it will be returned from there. If it isn't in the cache, it will be created using a
+	// backend specific function.
+	// Note that the reference count on the scaled font is increased each time this function
+	// is called. Therefore, releaseScaledFont() needs to be called once for each time
+	// getScaledFont() is called.
+	static cairo_scaled_font_t* getScaledFont(string family,
+	                                          double size,
+	                                          bool bold,
+	                                          bool italic,
+	                                          cairo_matrix_t ctm) {
+		if(!fontCache)
+			fontCache = new List!(FontCacheEntry);
+		// set the translation to zero so that
+		// 1. entryCtm == ctm can be used when searching through the cache, and it will still
+		//    ignore the translation
+		// 2. the CTM of every scaled font in the font cache has a translation of zero
+		ctm.x0 = 0;
+		ctm.y0 = 0;
+		foreach(entry; fontCache) {
+			if(entry.family == family && entry.size == size &&
+			   entry.bold == bold && entry.italic == italic) {
+				cairo_matrix_t entryCtm;
+				cairo_scaled_font_get_ctm(entry.font, &entryCtm);
+				// a font can only match another if they have the same CTM (except the
+				// transformation can be different), so check that the CTMs are the same
+				if(entryCtm == ctm) {
+					cairo_scaled_font_reference(entry.font);
+					return entry.font;
+				}
+			}
+		}
+
+		// since a matching font wasn't found in the cache, create it and add it to the cache
+		FontCacheEntry entry;
+		entry.font = backend_createScaledFont(family, size, bold, italic, &ctm);
+		entry.family = family;
+		entry.size = size;
+		entry.bold = bold;
+		entry.italic = italic;
+		fontCache.add(entry);
+		return entry.font;
+	}
+	// Decreases the reference count of the scaled font and removes it from the cache when its
+	// reference count reaches zero.
+	static void releaseScaledFont(cairo_scaled_font_t* font) {
+		if(cairo_scaled_font_get_reference_count(font) == 1) {
+			bool found = false;
+			foreach(i, entry; fontCache) {
+				if(entry.font == font) {
+					fontCache.removeAt(i);
+					found = true;
+					break;
+				}
+			}
+			assert(found);
+		}
+		cairo_scaled_font_destroy(font);
+	}
+	//}}}
 }
 
+struct FontCacheEntry {
+	cairo_scaled_font_t* font;
+	string family;
+	double size;
+	bool bold;
+	bool italic;
+}
+
+private List!(FontCacheEntry) fontCache; // global in D1, thread local in D2
+
+// this is to keep the TextLayout.runs List around until the destructor is called
+List!(List!(Run)) runLists;
+
 unittest {
 	auto t = new TextLayout("Tahoma", 15);
 	t.text = "How are you doing today?";
@@ -553,6 +1259,7 @@
 	t.setUnderline(LineStyle.None, 4, 20); // "are you doing today?"
 	assert(t.formatting.count == 0);
 }
+
 unittest {
 	auto t = new TextLayout("Arial", 14);
 	t.text = "The computer is black.";
@@ -598,3 +1305,116 @@
 	// TODO: test fontFormatRuns
 }
 
+unittest {
+	auto surf = cairo_image_surface_create(CAIRO_FORMAT_ARGB32, 1, 1);
+	auto cr = cairo_create(surf);
+	cairo_surface_destroy(surf);
+	auto g = new Graphics(cr);
+	cairo_destroy(cr);
+
+	// with 0 being the first line
+	void assertLineRange(TextLayout t, int line, int start, int length) {
+		float lastLineY;
+		int startAct = -1, lengthAct = -1; // actual start and length of line
+		foreach(run; t.runs) {
+			if(run.position.y != lastLineY) {
+				line--;
+				if(line == -1) {
+					startAct = run.start;
+				} else if(line == -2) {
+					lengthAct = run.start - startAct;
+					break;
+				}
+			}
+			lastLineY = run.position.y;
+		}
+		assert(startAct >= 0);
+		if(lengthAct == -1)
+			lengthAct = t.text.length - startAct;
+		Stdout.format("s {0} l {1} s2 {2} l2 {3}", start, length, startAct, lengthAct).newline;
+		assert(start == startAct && length == lengthAct);
+	}
+	void assertLinePosition(TextLayout t, int line, float x, float y) {
+		float lastLineY;
+		foreach(run; t.runs) {
+			if(run.position.y != lastLineY) {
+				line--;
+				if(line == -1) // test the x of the first run on the line
+					assert(run.position.x < x+0.01 && run.position.x > x-0.01);
+			}
+			if(line == -1)  // and test the y of every run on the line
+				assert(run.position.y < y+0.01 && run.position.y > y-0.01);
+			else if(line < -1)
+				break;
+			lastLineY = run.position.y;
+		}
+		assert(line < 0); // assert that there were enough lines
+	}
+
+	auto t = new TextLayout("Ahem", 10);
+	t.text = "The quick brown fox jumps over the lazy dog.";
+
+	// Test that lines are moved down when text on them is larger than the beginning.
+	// Test that the second line is not too tall, since no text on it is larger.
+	// Test that having a one character run at the end is handled correctly. (doesn't crash)
+	t.setFontSize(12, 15, 1); // " "
+	t.setFontSize(13, 16, 4); // "fox "
+	t.setFontSize( 8, 43, 1); // "."
+	t.layoutBoxes = [Rect(40, 30, 225, 100)];
+	//The quick brown fox /jumps over the lazy /dog./
+	t.draw(g);
+	assertLineRange(t, 0,  0, 20); // line 0 has first 20 chars
+	assertLineRange(t, 1, 20, 20); // line 1 has next 20 chars
+	assertLineRange(t, 2, 40,  4); // line 2 has next 4 chars
+	assertLinePosition(t, 0, 40, 30);
+	assertLinePosition(t, 1, 40, 43);
+	assertLinePosition(t, 2, 40, 53);
+
+	// Test that when runs are cut off due to not fitting in layout boxes,
+	// there is no assert failure in draw()
+	t.layoutBoxes = [Rect(40, 30, 225, 24)];
+	t.draw(g);
+
+	// Test that layout boxes work:
+	// that lines are wrapped to the width of the layout box and
+	// that they are positioned correctly vertically.
+	t.setFontSize(10, 0, t.text.length);
+	t.layoutBoxes = [Rect(20, 20, 170, 24), Rect(200, 1000, 60, 33)];
+	//The quick brown /fox jumps over /the /lazy /dog./
+	t.draw(g);
+	assertLineRange(t, 0,  0, 16);
+	assertLineRange(t, 1, 16, 15);
+	assertLineRange(t, 2, 31,  4);
+	assertLineRange(t, 3, 35,  5);
+	assertLineRange(t, 4, 40,  4);
+	assertLinePosition(t, 0,  20,   20);
+	assertLinePosition(t, 1,  20,   30);
+	assertLinePosition(t, 2, 200, 1000);
+	assertLinePosition(t, 3, 200, 1010);
+	assertLinePosition(t, 4, 200, 1020);
+
+/*
+test that the height of a run on a line is not set to the height of the line (stays the height of the text
+test that having taller text on a line, then shorter text, then that the next line is the right height
+test that text is broken for line boxes
+test having bigger text near end of line, and when line is moved down, first line box is smaller, so text is broken sooner
+test that if text needs to be moved down and fewer chars fit on, that it is not moved down
+*/
+
+	// Test that a whole word is put on a line, even when the layout box is not wide enough.
+	// Test that there is no crash when the first word is wider than the layout box.
+	t.text = "Somebodyforgottousespaces, oh, thisisbad, I say.";
+	t.layoutBoxes = [Rect(40, 30, 85, 50)];
+	t.draw(g);
+	assertLineRange(t, 0,  0, 27);
+	assertLineRange(t, 1, 27,  4);
+	assertLineRange(t, 2, 31, 11);
+	assertLineRange(t, 3, 42,  6);
+	assertLinePosition(t, 0, 40, 30);
+	assertLinePosition(t, 1, 40, 40);
+	assertLinePosition(t, 2, 40, 50);
+	assertLinePosition(t, 3, 40, 60);
+
+// write manual tests into showcase
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dynamin/painting/windows_text_layout.d	Wed May 02 03:19:00 2012 -0500
@@ -0,0 +1,497 @@
+// Written in the D programming language
+// www.digitalmars.com/d/
+
+/*
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is the Dynamin library.
+ *
+ * The Initial Developer of the Original Code is Jordan Miner.
+ * Portions created by the Initial Developer are Copyright (C) 2007-2012
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Jordan Miner <jminer7@gmail.com>
+ *
+ */
+
+module dynamin.painting.windows_text_layout;
+
+public import dynamin.c.cairo;
+public import dynamin.c.cairo_win32;
+public import dynamin.c.windows;
+public import dynamin.c.uniscribe;
+public import dynamin.painting.graphics;
+public import tango.io.Stdout;
+public import tango.text.convert.Utf;
+public import tango.math.Math;
+
+//version = TextLayoutDebug;
+
+// TODO: move to array.d
+bool containsT(T)(T[] array, T item) {
+	foreach(T item2; array) {
+		if(item == item2)
+			return true;
+	}
+	return false;
+}
+template TextLayoutBackend() {
+	uint charToWcharIndex(uint index) {
+		uint wcharIndex = 0;
+		foreach(wchar c; text[0..index])
+			wcharIndex++;
+		return wcharIndex;
+	}
+	uint wcharToCharIndex(uint wcharIndex) {
+		uint decoded = 0, ate = 0, index = 0;
+		while(decoded < wcharIndex) {
+			decoded += (decode(text[index..$], ate) <= 0xFFFF ? 1 : 2);
+			index += ate;
+		}
+		return index;
+	}
+
+	uint nextRight(uint index) {
+		uint wIndex = charToWcharIndex(index);
+		// this requires using the output from ScriptLayout to move in visual order
+		return 0;
+	}
+
+	//{{{ font fallback
+	static {
+		int Latin;
+		int Greek;
+		int Cyrillic;
+		int Armenian;
+		int Georgian;
+		int Hebrew;
+		int Arabic;
+		int Syriac;
+		int Thaana;
+		int Thai;
+		int Devanagari;
+		int Tamil;
+		int Bengali;
+		int Gurmukhi;
+		int Gujarati;
+		int Oriya;
+		int Telugu;
+		int Kannada;
+		int Malayalam;
+		int Lao;
+		int Tibetan;
+		//int Japanese;
+		int Bopomofo;
+		int CjkIdeographs;
+		int CjkSymbols;
+		int KoreanHangul;
+	}
+	static this() {
+		Latin              = getUniscribeScript("JKL");
+		Greek              = getUniscribeScript("ΠΡΣ");
+		Cyrillic           = getUniscribeScript("КЛМ");
+		Armenian           = getUniscribeScript("ԺԻԼ");
+		Georgian           = getUniscribeScript("ႩႪႫ");
+		Hebrew             = getUniscribeScript("הוז");
+		Arabic             = getUniscribeScript("ثجح");
+		Syriac             = getUniscribeScript("ܕܗܚ");
+		Thaana             = getUniscribeScript("ގޏސ");
+		Thai               = getUniscribeScript("ฆงจ");
+		Devanagari         = getUniscribeScript("जझञ");
+		Tamil              = getUniscribeScript("ஜஞட");
+		Bengali            = getUniscribeScript("জঝঞ");
+		Gurmukhi           = getUniscribeScript("ਜਝਞ");
+		Gujarati           = getUniscribeScript("જઝઞ");
+		Oriya              = getUniscribeScript("ଜଝଞ");
+		Telugu             = getUniscribeScript("జఝఞ");
+		Kannada            = getUniscribeScript("ಜಝಞ");
+		Malayalam          = getUniscribeScript("ജഝഞ");
+		Lao                = getUniscribeScript("ຄງຈ");
+		Tibetan            = getUniscribeScript("ཇཉཊ");
+		//Japanese           = getUniscribeScript("せゼｶ"); // TODO: on XP, returned more than 1 item
+		Bopomofo           = getUniscribeScript("ㄐㄓㄗ"); // Chinese
+		CjkIdeographs      = getUniscribeScript("丛东丝");
+		CjkSymbols         = getUniscribeScript("、〜㈬");
+		KoreanHangul       = getUniscribeScript("갠흯㉡");
+	}
+	// returns the Uniscribe script number (SCRIPT_ANALYSIS.eScript) from the specified sample text
+	static int getUniscribeScript(wchar[] sample) {
+		SCRIPT_ITEM[5] items;
+		int itemsProcessed;
+		HRESULT r = ScriptItemize(sample.ptr,
+		                          sample.length,
+		                          items.length-1,
+		                          null,
+		                          null,
+		                          items.ptr,
+		                          &itemsProcessed);
+		assert(r == 0);
+		assert(itemsProcessed == 1);
+		return items[0].a.eScript.get();
+	}
+
+	// adds fallback fonts to the specified fallbacks array
+	void getFontFallbacks(int script, wchar[][] fallbacks) {
+		int i = 0;
+		void addFallback(wchar[] str) {
+			fallbacks[i++] = str;
+		}
+		if(script == Latin || script == Greek || script == Cyrillic)
+			addFallback("Times New Roman");
+		else if(script == Hebrew || script == Arabic)
+			addFallback("Times New Roman");
+		else if(script == Armenian || script == Georgian)
+			addFallback("Sylfaen"); // fits in well with English fonts
+		else if(script == Bengali)
+			addFallback("Vrinda");
+		else if(Devanagari)
+			addFallback("Mangal");
+		else if(script == Gujarati)
+			addFallback("Shruti");
+		else if(script == Gurmukhi)
+			addFallback("Raavi");
+		else if(script == Kannada)
+			addFallback("Tunga");
+		else if(script == Malayalam)
+			addFallback("Kartika");
+		else if(script == Syriac)
+			addFallback("Estrangelo Edessa");
+		else if(script == Tamil)
+			addFallback("Latha");
+		else if(script == Telugu)
+			addFallback("Gautami");
+		else if(script == Thaana)
+			addFallback("MV Boli");
+		else if(script == Thai)
+			addFallback("Tahoma"); // fits in well with English fonts
+		//else if(script == Japanese)
+		//	addFallback("MS Mincho"); // Meiryo doesn't fit in with SimSun...
+		else if(script == Bopomofo || script == CjkIdeographs || script == CjkSymbols)
+			addFallback("SimSun");
+		else if(script == KoreanHangul)
+			addFallback("Batang");
+		else if(script == Oriya)
+			addFallback("Kalinga");    // new with Vista
+		else if(script == Lao)
+			addFallback("DokChampa");  // new with Vista
+		else if(script == Tibetan)
+			addFallback("Microsoft Himalaya"); // new with Vista
+
+		// Arial Unicode MS is not shipped with Windows, but is with Office
+		addFallback("Arial Unicode MS");
+	}
+	//}}}
+
+	/*bool isRightAligned() {
+		return alignment == TextAlignment.Right ||
+		       ((alignment == TextAlignment.Justify || alignment == TextAlignment.Natural) &&
+		        items[0].a.fRTL);
+	}*/
+	/*struct Run {
+		double height;
+		int wtextIndex;
+		int itemIndex;
+		WORD[] logClusters;        // length == length of text as UTF-16
+		WORD[] glyphs;
+		SCRIPT_VISATTR[] visAttrs; // length == glyphs.length
+		int[] advanceWidths;       // length == glyphs.length
+		GOFFSET[] offsets;         // length == glyphs.length
+	}*/
+	// TODO: should save memory if logClusters, glyphs, visAttrs, advanceWidths, & offsets
+	//       were made as one big array and these were just slices of them
+	//       Then reuse the big array every time in layout()
+
+	void backend_splitRun(uint runIndex, uint splitIndex) {
+		visAttrs.insert(visAttrs[runIndex], runIndex);
+		visAttrs[runIndex]   = visAttrs[runIndex][0..runs[runIndex].glyphs.length];
+		visAttrs[runIndex+1] = visAttrs[runIndex+1][runs[runIndex].glyphs.length..$];
+
+		offsets.insert(offsets[runIndex], runIndex);
+		offsets[runIndex]   = offsets[runIndex][0..runs[runIndex].glyphs.length];
+		offsets[runIndex+1] = offsets[runIndex+1][runs[runIndex].glyphs.length..$];
+	}
+	// returns the number of UTF-8 code units (bytes) it takes to encode the
+	// specified UTF-16 code unit; returns 4 for a high surrogate and 0 for a low surrogate
+	int getUtf8Width(wchar c) {
+		if(c >= 0x00 && c <= 0x7F) {
+			return 1;
+		} else if(c >= 0x0080 && c <= 0x07FF) {
+			return 2;
+		} else if(isHighSurrogate(c)) {
+			return 4;
+		} else if(isLowSurrogate(c)) {
+			return 0;
+		} else {
+			return 3;
+		}
+	}
+
+	SCRIPT_ITEM[] items;
+	List!(SCRIPT_VISATTR[]) visAttrs; // one for each Run, same length as Run.glyphs
+	List!(GOFFSET[]) offsets;         // one for each Run, same length as Run.glyphs
+	void backend_preprocess(Graphics g) {
+		wchar[] wtext = toString16(text);
+
+		//{{{ call ScriptItemize() and ScriptBreak()
+		SCRIPT_CONTROL scriptControl;
+		SCRIPT_STATE scriptState;
+		// TODO: digit substitution?
+
+		if(items.length < 50)
+			items.length = 50;
+		int itemsProcessed;
+		// On 7, ScriptItemize returns E_OUTOFMEMORY outright if the 3rd param isn't at least 12.
+		// Every period, question mark, quotation mark, start of number, etc. starts a new item.
+		// A short English sentence can easily have 10 items.
+		while(ScriptItemize(wtext.ptr,
+		                    wtext.length,
+		                    items.length-1,
+		                    &scriptControl,
+		                    &scriptState,
+		                    items.ptr,
+		                    &itemsProcessed) == E_OUTOFMEMORY) {
+			items.length = items.length * 2;
+		}
+		items = items[0..itemsProcessed+1]; // last item is the end of string
+
+		for(int i = 0; i < logAttrs.length; ++i) // clear array from previous use
+			logAttrs[i] = LogAttr.init;
+		logAttrs.length = text.length;
+		int laIndex = 0;
+
+		SCRIPT_LOGATTR[] tmpAttrs;
+		bool lastWhitespace = false;
+		for(int i = 0; i < items.length-1; ++i) {
+			wchar[] itemText = wtext[items[i].iCharPos..items[i+1].iCharPos];
+			tmpAttrs.length = itemText.length;
+			HRESULT result = ScriptBreak(itemText.ptr, itemText.length, &items[i].a, tmpAttrs.ptr);
+			if(FAILED(result))
+				throw new Exception("ScriptBreak() failed");
+
+			// ScriptBreak() does not set fSoftBreak for the first character of items, even
+			// when it needs to be (it doesn't know what comes before them...). This loop sets
+			// it for characters after a breakable whitespace.
+			for(int j = 0; j < tmpAttrs.length; ++j) {
+				if(tmpAttrs[j].fWhiteSpace.get()) {
+					lastWhitespace = true;
+				} else {
+					if(lastWhitespace) // not whitespace, but last char was
+						tmpAttrs[j].fSoftBreak.set(true);
+					lastWhitespace = false;
+				}
+
+				// have to convert the SCRIPT_LOGATTR array, which corresponds with the UTF-16
+				// encoding, to the LogAttr array, which corresponds with the UTF-8 encoding
+				if(tmpAttrs[j].fSoftBreak.get())
+					logAttrs[laIndex].softBreak = true;
+				if(tmpAttrs[j].fCharStop.get())
+					logAttrs[laIndex].clusterStart = true;
+				if(tmpAttrs[j].fWordStop.get())
+					logAttrs[laIndex].wordStart = true;
+
+				laIndex += getUtf8Width(itemText[j]);
+				if(isHighSurrogate(itemText[j]))
+					j++; // skip the low surrogate
+			}
+		}
+		assert(laIndex == logAttrs.length);
+		//}}}
+
+		// ScriptShape and some other functions need an HDC. If the target surface is win32,
+		// just use its DC. Otherwise, create a 1x1 DIB and use its DC.
+		cairo_surface_t* targetSurface = cairo_get_target(g.handle);
+		cairo_surface_flush(targetSurface);
+		cairo_t* cr = g.handle;
+		HDC hdc = cairo_win32_surface_get_dc(targetSurface);
+		cairo_surface_t* tmpSurface;
+		if(!hdc) {
+			cairo_format_t format = CAIRO_FORMAT_ARGB32;
+			if(cairo_surface_get_type(targetSurface) == CAIRO_SURFACE_TYPE_IMAGE)
+				format = cairo_image_surface_get_format(targetSurface);
+			tmpSurface = cairo_win32_surface_create_with_dib(format, 1, 1);
+			cr = cairo_create(tmpSurface);
+			hdc = cairo_win32_surface_get_dc(tmpSurface);
+			assert(hdc != null);
+		}
+		scope(exit) {
+			if(tmpSurface) {
+				cairo_destroy(cr);
+				cairo_surface_destroy(tmpSurface);
+			}
+		}
+
+		clearRuns(); // releaseScaledFont() must be called when a run is removed
+
+		if(!visAttrs)
+			visAttrs = new List!(SCRIPT_VISATTR[]);
+		visAttrs.clear();
+		if(!offsets)
+			offsets = new List!(GOFFSET[]);
+		offsets.clear();
+		List!(BYTE) levels = new List!(BYTE)(items.length+4); // 4 gives padding for 2 formattings
+
+		SaveDC(hdc);
+		int splitter(uint i) {
+			return i < items.length ? wcharToCharIndex(items[i].iCharPos) : -1;
+		}
+		int itemIndex = 0;
+		// Merge the SCRIPT_ITEMs with runs that have the same format
+		// The only formats that matter here are the ones that affect the size or
+		// shape of characters, so use &fontFormatRuns
+		foreach(start, length, format; fontFormatRuns(&splitter)) {
+			uint wstart = charToWcharIndex(start);
+			uint wend = charToWcharIndex(start+length);
+			if(items[itemIndex+1].iCharPos == wstart)
+				itemIndex++;
+
+			levels.add(items[itemIndex].a.s.uBidiLevel.get());
+
+			cairo_matrix_t ctm;
+			cairo_get_matrix(cr, &ctm);
+			cairo_scaled_font_t* font = getScaledFont(format.fontFamily,
+													  format.fontSize,
+													  format.bold,
+													  format.italic,
+													  ctm);
+			cairo_win32_scaled_font_select_font(font, hdc);
+			// Cairo sets up the HDC to be scaled 32 times larger than stuff will be drawn.
+			// get_metrics_factor returns the factor necessary to convert to font space units.
+			// Font space units need multiplied by the font size to get device units
+			// multipling by to_dev converts from logical units to device units
+			double to_dev = cairo_win32_scaled_font_get_metrics_factor(font) * format.fontSize;
+
+			SCRIPT_CACHE cache = null;
+			scope(exit) ScriptFreeCache(&cache);
+
+			wchar[] range = wtext[wstart..wend];
+
+			WORD[] outGlyphs = new WORD[range.length * 3 / 2 + 16];
+			WORD[] logClust = new WORD[range.length];
+			SCRIPT_VISATTR[] sva = new SCRIPT_VISATTR[outGlyphs.length];
+			int glyphsReturned;
+			do {
+				HRESULT result = ScriptShape(hdc,
+											 &cache,
+											 range.ptr,
+											 range.length,
+											 outGlyphs.length,
+											 &items[itemIndex].a,
+											 outGlyphs.ptr,
+											 logClust.ptr,
+											 sva.ptr,
+											 &glyphsReturned);
+				if(result == E_OUTOFMEMORY) {
+					outGlyphs.length = outGlyphs.length * 3 / 2;
+					sva.length = outGlyphs.length;
+					continue;
+				} else if(result == USP_E_SCRIPT_NOT_IN_FONT) {
+					// TODO: font fallback
+				}
+				/*SCRIPT_FONTPROPERTIES fontProps;
+				ScriptGetFontProperties(hdc, &cache, &fontProps);
+				Stdout("*****Blank: ")(fontProps.wgBlank).newline;
+				Stdout(fontProps.wgDefault).newline;*/
+			} while(false);
+			outGlyphs = outGlyphs[0..glyphsReturned];
+			sva = sva[0..glyphsReturned];
+			visAttrs.add(sva);
+
+			int[] advance = new int[outGlyphs.length];
+			GOFFSET[] goffset = new GOFFSET[outGlyphs.length];
+			// the docs mistakenly say the GOFFSET array is optional,
+			// but it is actually the ABC structure
+			if(FAILED(ScriptPlace(hdc,
+								  &cache,
+								  outGlyphs.ptr,
+								  outGlyphs.length,
+								  sva.ptr,
+								  &items[itemIndex].a,
+								  advance.ptr,
+								  goffset.ptr,
+								  null)))
+				throw new Exception("ScriptPlace failed");
+			for(int i = 0; i < goffset.length; ++i) {
+				goffset[i].du = cast(LONG)(goffset[i].du * to_dev);
+				goffset[i].dv = cast(LONG)(goffset[i].dv * to_dev);
+			}
+			offsets.add(goffset);
+			// TODO: handle errors well
+			// TODO: kerning here
+
+			Run run;
+			run.font = font;
+			cairo_font_extents_t extents;
+			cairo_scaled_font_extents(run.font, &extents);
+			run.height = extents.height;
+
+			run.start = start;
+			run.length = length;
+			run.rightToLeft = items[itemIndex].a.fRTL.get() ? true : false;
+
+			run.clusterMap = new uint[run.length];
+			int clusterIndex = 0;
+			for(int i = 0; i < logClust.length; ++i) {
+				int width = getUtf8Width(range[i]);
+				if(isHighSurrogate(range[i]))
+					i++; // skip the low surrogate
+				for(; width > 0; --width) {
+					run.clusterMap[clusterIndex] = logClust[i];
+					clusterIndex++;
+				}
+			}
+			assert(clusterIndex == run.length);
+
+			run.glyphs = new uint[outGlyphs.length];
+			for(int i = 0; i < outGlyphs.length; ++i)
+				run.glyphs[i] = outGlyphs[i];
+
+			run.advanceWidths = new float[advance.length];
+			for(int i = 0; i < advance.length; ++i)
+				run.advanceWidths[i] = advance[i] * to_dev;
+
+			runs.add(run);
+
+			cairo_win32_scaled_font_done_font(font);
+
+		}
+		RestoreDC(hdc, -1);
+		assert(itemIndex == items.length-2); // last item is end of string
+
+		// fill in visToLogMap
+		visToLogMap = new uint[runs.count];
+		if(FAILED( ScriptLayout(levels.count, levels.data.ptr, cast(int*)visToLogMap.ptr, null) ))
+			throw new Exception("ScriptLayout() failed");
+
+	}
+
+	static cairo_scaled_font_t* backend_createScaledFont(string family,
+	                                                     double size,
+	                                                     bool bold,
+	                                                     bool italic,
+	                                                     cairo_matrix_t* ctm) {
+		LOGFONT lf;
+		lf.lfHeight = -cast(int)size; // is this ignored by cairo? uses font_matrix instead?
+		lf.lfWeight = bold ? 700 : 400;
+		lf.lfItalic = italic;
+		lf.lfCharSet = 1; // DEFAULT_CHARSET
+		auto tmp = toString16(family);
+		lf.lfFaceName[0..tmp.length] = tmp;
+		lf.lfFaceName[tmp.length] = '\0';
+
+		auto face = cairo_win32_font_face_create_for_logfontw(&lf);
+		scope(exit) cairo_font_face_destroy(face);
+
+		cairo_matrix_t font_matrix;
+		cairo_matrix_init_scale(&font_matrix, size, size);
+		return cairo_scaled_font_create(face, &font_matrix, ctm, cairo_font_options_create());
+	}
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dynamin/painting_backend.d	Wed May 02 03:19:00 2012 -0500
@@ -0,0 +1,31 @@
+// Written in the D programming language
+// www.digitalmars.com/d/
+
+/*
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is the Dynamin library.
+ *
+ * The Initial Developer of the Original Code is Jordan Miner.
+ * Portions created by the Initial Developer are Copyright (C) 2007-2012
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *   Jordan Miner <jminer7@gmail.com>
+ *
+ */
+
+module dynamin.painting_backend;
+
+version(Windows) {
+	public import dynamin.painting.windows_text_layout;
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/text.d	Wed May 02 03:19:00 2012 -0500
@@ -0,0 +1,165 @@
+// testing with word العربية al-arabiyyah
+
+/*
+I may need to keep some info around (especially advance widths) so I can pass it to ScriptCPtoX(), ScriptXtoCP(), and other functions.
+
+First, call ScriptItemize(). It will return *items* that have one script and direction.
+
+My code will have a list of ranges where the formatting is the same. I need to split the items from ScriptItemize() into *runs* that have the same format, script, and direction. The run is an array of WCHARs (should be a slice).
+
+Then, I call ScriptShape once for each of these runs, and it returns an array of the glyphs, among other things.
+
+Now that I have the glyphs, I can pass them to ScriptPlace(), which returns an array of the advance widths for each of them. (By default they are in visual order, but you can request them in logical order.) I can edit these to apply the letter spacing. Kerning would also take place here, I believe. I think I would edit tab widths here too.
+
+If the text needs justified, I can call ScriptJustify() with the advance widths (and other data) for the entire line. It will return updated advance widths.
+
+I can call ScriptBreak() for each item from ScriptItemize(), passing it the info for the item. It will return an array with:
+
+- Places in the item where it can be broken across lines
+- Places in the item that the caret can move when left or right is pressed
+- Places in the item the caret can move when Ctrl+Left/Right is pressed (words)
+*/
+
+import tango.io.Stdout;
+import dynamin.c.windows;
+import dynamin.core.string;
+import dynamin.painting.text_layout;
+import dynamin.all;
+extern(Windows):
+int callback(ENUMLOGFONTEX* elf, TEXTMETRIC*, DWORD, LPARAM) {
+	int i = 0;
+	for(; i < LF_FULLFACESIZE; i++)
+		if(elf.elfFullName[i] == 0)
+			break;
+
+	int j = 0;
+	for(; j < LF_FACESIZE; j++)
+		if(elf.elfStyle[j] == 0)
+			break;
+
+	Stdout(elf.elfFullName[0..i])(" ... ")(elf.elfStyle[0..j]).newline;
+	return 1;
+}
+
+void main() {
+	//string text = "The first text to draw.";
+
+	// a reasonable size of a paragraph
+	//scope buf = new wchar[text.length < 256 ? 256 : 1536];
+	//wchar[] wtext = text.toString16(buf);
+
+	LOGFONT lf;
+	lf.lfCharSet = 1; // DEFAULT_CHARSET
+	lf.lfFaceName[0] = '\0';
+	//EnumFontFamiliesEx(GetDC(null), &lf, &callback, 0, 0);
+	Window w = new Window;
+	w.text = "TextLayout test";
+	auto t = new TextLayout("Garamond", 20);
+	//t.text = "John said, 'I bought 24 eggs.' How many did you buy?";
+	t.text = "Whenyouhaveareallylongword you approach -look, colors!- Fort Sutch, you will encounter a group of Imperial Guards, including an Imperial Guard Captain, who will request your assistance in defeating the Daedra pouring out of the nearby Oblivion Gate. The final Daedra you will need to defeat will be a leveled Dremora, who will emerge through the Gate as you approach it. When all the Daedra are defeated, return to the Captain. Speak with him, he will tell you to close the gate if you wish, but informs you that he will be staying at Fort Sutch per his orders.";
+	//t.setForeColor(Color.Blue, 26, 5);
+	t.setBold(true, 5, 4);
+	t.setItalic(true, 2, 7);
+	t.setFontFamily("Tahoma", 31, 3);
+	t.setFontSize(35, 35, 4);
+	t.setForeColor(Color.Blue, 40, 7);
+	t.setForeColor(Color.Red, 47, 8);
+	t.setBackColor(Color.Gold, 47, 8);
+	w.content.painting += (PaintingEventArgs args) {
+		try {
+			t.draw(args.graphics);
+		} catch(Exception e) {
+			Stdout("Exception: (")(e.line)(") ")(e.msg).newline;
+		}
+	};
+	w.content.resized += {
+		auto sz = w.content.size;
+		t.layoutBoxes = [Rect(0, 0, sz.width/2, sz.height/2), Rect(sz.width/2, sz.height/2, sz.width/2, sz.height/2)];
+	};
+	w.size = [640, 480];
+
+	w.visible = true;
+	Application.run(w);
+
+}
+/*
+// Build thorough tests into showcase
+class TextParagraph {
+	// support kerning? GetKerningPairs() and KERNINGPAIR
+	void layout(char[] text, ) {
+	}
+
+	char[] text;
+	Tab[] tabs;
+	uint defaultTabLocations = 0; // no default tabs
+	// newLineSpacing = old * mul + delta
+	// spacing after line, as part of it
+	real lineSpacingMul = 1.0;   // percent
+	real lineSpacingDelta = 0; // pixels
+	Alignment alignment;
+
+	uint width;
+	delegate wrap
+
+}
+// Word uses SOH as placeholder for embedded obj
+// Word uses VT for a soft return
+
+struct Tab {
+	int location;
+	TabType type;
+	TabLeading leading;
+}
+struct EmbeddedObject {
+	Point location;
+	Size size;
+}
+Format {
+	string family;
+	real size;
+	bool bold;
+	bool italic;
+	// spaces are not underlined, overlined, or strikethrough unless
+	// words on both sides are
+	LineStyle underlined;
+	LineStyle strikethrough;
+	LineStyle overlined;
+	bool superscript; // 2/3 of the height
+	bool subscript;   // 2/3 of the height
+	real letterSpacingMul = 1.0; // after letter, as part of it
+	real letterSpacingAdd = 0;
+	// ( ^ useful for Hexplore's column spacing)
+	Color foreColor;
+	Color backColor;
+
+
+	offsetof
+}
+// underline, strikethrough, and overline line styles
+enum LineStyle {
+	None,
+	Single,
+	Double,
+	Dotted,
+	Dashed,
+	Wavy
+}
+FormatChange {
+	FormatType type;
+	void apply(ref Format format) {
+
+	}
+	union Data {
+		string family;
+		real size;
+		bool on; // bold and italic
+		LineStyle lineStyle;
+		real letterSpacing;
+		Color color;
+	}
+}
+enum FormatType : ubyte {
+	Family, Size, Bold, Italic, Underline, Strikethrough, Overline,
+
+}
+*/