Process HTML text for directionality.

After we parse html text from an ebook run it through the
unicode bidirectional algorithm to determine the directionality
of each fragment. This may require splitting of fragments.

Currently we don't do anything with this information.

4 files changed, 275 insertions, 218 deletions

diff --git a/include/mupdf/fitz/bidi.h b/include/mupdf/fitz/bidi.h
index 0b5b9553..978696ef 100644
--- a/include/mupdf/fitz/bidi.h
+++ b/include/mupdf/fitz/bidi.h
@@ -199,6 +199,61 @@ Bidi_Direction Bidi_processLine(fz_context *ctx,
                                 int                        *more);
 
 
+int Bidi_isEuropeanNumber(const uint16_t *str, unsigned int len);
+
+/**
+ * returns a character's mirrored equivalent
+ *
+ * @param     u     Unicode character to process
+ */
+uint16_t Bidi_mirrorChar(const uint16_t u);
+
+
+
+/**
+ * Prototype for callback function supplied to Bidi_fragmentText.
+ *
+ * @param     fragment      first character in fragment
+ * @param     fragmentLen   number of characters in fragment
+ * @param     rightToLeft   true if fragment is right-to-left
+ * @param     mirror        The mirror code of the fragment if it exists
+ * @param     arg           data from caller of Bidi_fragmentText
+ */
+typedef void (Bidi_Fragment_Callback)(const uint16_t *fragment,
+					size_t fragmentLen,
+					int rightToLeft,
+					uint16_t mirror,
+					void *arg);
+
+
+
+/**
+ * Partitions the given Unicode sequence into one or more unidirectional
+ * fragments and invokes the given callback function for each fragment.
+ *
+ * For example, if directionality of text is:
+ *               0123456789
+ *               rrlllrrrrr,
+ * we'll invoke callback with:
+ *               &text[0], length == 2, rightToLeft ==  true
+ *               &text[2], length == 3, rightToLeft == false
+ *               &text[5], length == 5, rightToLeft ==  true.
+ *
+ * @param[in] text      start of Unicode sequence
+ * @param[in] textlen   number of Unicodes to analyse
+ * @param[in] baseDir   direction of paragraph (specify Bidi_Neutral
+ *                      to force auto-detection)
+ * @param[in] callback  function to be called for each fragment
+ * @param[in] arg       data to be passed to the callback function
+ * @param[in] bidiFlag  flag to be passed to the callback function
+ */
+void Bidi_fragmentText(fz_context *ctx,
+			const uint16_t *text,
+			size_t textlen,
+			Bidi_Direction *baseDir,
+			Bidi_Fragment_Callback callback,
+			void *arg,
+			int bidiFlag);
 
 #endif /* BIDI_BIDI_H */
 
diff --git a/include/mupdf/html.h b/include/mupdf/html.h
index 830c95f8..3955aebc 100644
--- a/include/mupdf/html.h
+++ b/include/mupdf/html.h
@@ -188,10 +188,31 @@ enum
 	FLOW_IMAGE = 3
 };
 
+/* We have to recognise the distinction between render direction
+ * and layout direction. For most strings render direction and
+ * logical direction are the same.
+ *
+ * Char direction determines whether a string 'ABC' appears as
+ * ABC or CBA.
+ *
+ * Block direction determines how fragments are attached together.
+ * 'ABC' and 'DEF' with r2l char and block directions will
+ * appear as 'FEDCBA'. With l2r char and block it will appear
+ * as 'ABCDEF'.
+ *
+ * The reason for the distinction is that we can have logical
+ * strings like 'ABC0123DEF', where 'ABC' and 'DEF' are in r2l
+ * scripts. The bidirectional code breaks this down into 3 fragments
+ * 'ABC' '0123' 'DEF', where all three are r2l, but digits need to
+ * be rendered left to right. i.e. the desired result is:
+ * FED0123CBA, rather than FED3210CBA.
+ */
 struct fz_html_flow_s
 {
 	unsigned int type : 2;
 	unsigned int expand : 1;
+	unsigned int char_r2l : 1;
+	unsigned int block_r2l : 1;
 	float x, y, w, h, em;
 	fz_css_style *style;
 	char *text;
diff --git a/source/fitz/bidi.c b/source/fitz/bidi.c
index a3bbbc1d..59d1578a 100644
--- a/source/fitz/bidi.c
+++ b/source/fitz/bidi.c
@@ -35,7 +35,6 @@
 
 #include "mupdf/fitz.h"
 #include "bidi-impl.h" /* standard bidi code interface */
-#include "bidi-internal.h"
 
 /*
  * Macros...
@@ -548,7 +547,6 @@ Bidi_CharType Bidi_classFromChN(uint16_t ch)
 }
 
 
-static
 int Bidi_isEuropeanNumber(const uint16_t *str, unsigned int len)
 {
 	const uint16_t *end = str + len;
@@ -650,32 +648,6 @@ uint16_t Bidi_mirrorChar(const uint16_t u)
 	return UNICODE_EOS;
 }
 
-#ifdef BIDI_LINE_AT_A_TIME
-/** Subsitutes characters with their mirrored equivalents, e.g. swaps
-  * '(' with ')'. Implements rule L4 of the uint16_t Bidirectional
-  * algorithm. Mirrored characters are found using a binary search through
-  * the lookup table bidiOptMirrorList.
-  */
-static
-void Bidi_mirror(uint16_t *text,
-		const Bidi_Level *poslevel,
-		int len)
-{
-	int i;
-	uint16_t out;
-
-	for (i = 0; i < len; i ++)
-	{
-		if (ODD(poslevel[i]) == 0)
-			continue;
-		out = Bidi_mirrorChar((const uint16_t)text[i]);
-		if(out != UNICODE_EOS)
-			text[i] = out;
-	}
-}
-#endif
-
-
 /** Searches a RTL fragment for a mirror character
  * When it finds one it creates a separate fragment for the
  * character and the surrounding fragments. It passes the mirrored
@@ -766,11 +738,15 @@ void Bidi_classifyCharacters(const uint16_t *text,
 				 );
 		}
 		fprintf(stderr, "\nTypes:  ");
+#endif
 		for (i = 0; i < len; i++)
 		{
 			types[i] = Bidi_classFromChN(text[i]);
+#ifdef DEBUG_BIDI_VERBOSE
 			fprintf(stderr, "%c", charFromTypes[(int)types[i]]);
+#endif
 		}
+#ifdef DEBUG_BIDI_VERBOSE
 		fprintf(stderr, "\n");
 #endif
 	}
@@ -1117,193 +1093,3 @@ void Bidi_fragmentText(fz_context *ctx,
 		fz_rethrow(ctx);
 	}
 }
-
-
-
-static void newFragCb(const uint16_t *fragment,
-			size_t fragmentLen,
-			int rightToLeft,
-			uint16_t mirror,
-			void *arg)
-{
-	size_t fragOffset;
-	int isRtlNumber = FALSE;
-	Bidi_ProcessLine_fragData *fragData = arg;
-
-	assert(fragData != NULL);
-
-	fragOffset = fragment - fragData->entireText;
-
-	if((fragOffset != 0) &&
-	   Bidi_isEuropeanNumber(fragment,fragmentLen))
-	{
-		/* fragment contains digits only */
-		isRtlNumber = TRUE;
-	}
-	fragData->callersCallback(fragOffset,
-				fragmentLen,
-				rightToLeft,
-				mirror,
-				fragData->callersData,
-				isRtlNumber);
-}
-
-
-
-/* Currently this creates a text representation of all the objects
- * on a line, then passes it to Bidi_fragmentText.  In future, we
- * should create the levels array directly from the objects supplied.
- */
-Bidi_Direction Bidi_processLine(fz_context *ctx,
-				Bidi_PL_NextObj_Callback nextObjCb,
-				Bidi_PL_Fragment_Callback fragmentCb,
-				void *callerData,
-				int bidiFlag,
-				int *more)
-{
-	uint16_t *entireText = NULL;
-	size_t entireLength = 0;
-	size_t lengthIncrement = 100;
-	size_t freeSpace = 0;
-	const uint16_t *objText = NULL;
-	size_t objLength = 0;
-	Bidi_Direction explicitDirection = Bidi_Neutral;
-
-	fz_var(entireText);
-
-	fz_try(ctx)
-	{
-		do
-		{
-			/* Call the client-supplied function to get the next object. */
-			nextObjCb(callerData, &objText, &objLength, more, &explicitDirection);
-			if (objText == NULL || objLength == 0)
-			{
-				/* End of sequence, or caller is giving us rubbish. */
-				break;
-			}
-
-			if (freeSpace < objLength)
-			{
-				/* We need a bigger buffer. */
-				uint16_t *newBuffer = NULL;
-				size_t increment = (objLength < lengthIncrement) ?
-							lengthIncrement : objLength;
-				/* Accommodate the string terminator that ustrncat will write */
-				if (entireText == NULL)
-				{
-					/* First Time. Add extra byte */
-					entireLength += increment + 1;
-				}
-				else
-				{
-					entireLength += increment;
-				}
-				newBuffer = fz_resize_array(ctx, entireText, entireLength, sizeof(uint16_t));
-				if (entireText == NULL)
-				{
-					/* First time.  Pretend buffer holds an empty string. */
-					newBuffer[0] = UNICODE_EOS;
-				}
-				entireText = newBuffer;
-				freeSpace += increment;
-			}
-			ustrncat (entireText, objText, objLength);
-
-			freeSpace -= objLength;
-		}
-		while (objText != NULL);
-
-		if (entireText != NULL)
-		{
-			size_t  i;
-			size_t  length = entireLength - 1 - freeSpace;
-			Bidi_ProcessLine_fragData fragData;
-			/* replace TAB character with SPACE for html Documents */
-			if((bidiFlag & Bidi_replaceTab) != 0)
-			{
-				for (i = 0; i < length; i++)
-				{
-					if (entireText[i]=='\t')
-					{
-						entireText[i] = ' ';
-					}
-				}
-			}
-
-			fragData.entireText	  = entireText;
-			fragData.callersCallback = fragmentCb;
-			fragData.callersData	 = callerData;
-			Bidi_fragmentText(ctx,
-					entireText,
-					length, &explicitDirection,
-					newFragCb, &fragData,
-					bidiFlag);
-		}
-	}
-	fz_always(ctx)
-	{
-		fz_free(ctx, entireText);
-	}
-	fz_catch(ctx)
-	{
-		fz_rethrow(ctx);
-	}
-
-	return explicitDirection;
-}
-
-
-#ifdef BIDI_LINE_AT_A_TIME
-/* This changes the given text by reordering and possibly mirroring
- * characters.  Suitable only for a single line of text.
- */
-void Bidi_processText(fz_context *ctx,
-			uint16_t *text,
-			Bidi_Direction baseDirection,
-			Bidi_Direction outputDirection,
-			int len)
-{
-	Bidi_Level *levels;
-
-	if (text == NULL || len == 0)
-	{
-		return;
-	}
-
-	levels = createLevels(ctx, text, (size_t)len, &baseDirection, TRUE, 0);
-
-	assert (levels != NULL);
-
-	/* resolve mirrored characters, e.g. swap '(' with ')' */
-	Bidi_mirror(text, levels, len);
-
-	(void)Bidi_reorder(baseDirection, text, levels, len);
-
-	/* reverse the string */
-	if (outputDirection == Bidi_RightToLeft)
-		ustrnreverse(text, len);
-
-#ifdef DEBUG_BIDI_VERBOSE
-	fprintf(stderr, "Done:   ");
-	{
-		int i;
-		for (i = 0; i < len; i++)
-		{
-			/* So that we can actually sort of read the debug string, any
-			 * non-ascii characters are replaced with a 1-digit hash
-			 * value from 0-9, making non-english characters appear
-			 * as numbers
-			 */
-			fprintf(stderr, "%c", (text[i] <= 127 && text[i ]>= 32)?
-								 text[i]
-								:(char)((text[i] % 9) + 48)
-				  );
-		}
-		fprintf(stderr, "\n\n");
-	}
-#endif
-
-	fz_free(ctx, levels);
-}
-#endif
diff --git a/source/html/html-layout.c b/source/html/html-layout.c
index ad3dd621..5bfcac85 100644
--- a/source/html/html-layout.c
+++ b/source/html/html-layout.c
@@ -116,6 +116,33 @@ static void add_flow_image(fz_context *ctx, fz_pool *pool, fz_html *top, fz_css_
 	add_flow_glue(ctx, pool, top, style, "", 0);
 }
 
+static fz_html_flow *split_flow(fz_context *ctx, fz_pool *pool, fz_html_flow *flow, size_t offset)
+{
+	fz_html_flow *new_flow;
+	char *text;
+	size_t len;
+
+	if (offset == 0)
+		return flow;
+	new_flow = fz_pool_alloc(ctx, pool, sizeof *flow);
+	*new_flow = *flow;
+	new_flow->next = flow->next;
+	flow->next = new_flow;
+
+	text = flow->text;
+	while (*text && offset)
+	{
+		int rune;
+		text += fz_chartorune(&rune, text);
+		offset--;
+	}
+	len = strlen(text);
+	new_flow->text = fz_pool_alloc(ctx, pool, len+1);
+	strcpy(new_flow->text, text);
+	*text = 0;
+	return new_flow;
+}
+
 static int iscjk(int c)
 {
 	if (c >= 0x3200 && c <= 0x9FFF) return 1; /* CJK Blocks */
@@ -1347,6 +1374,172 @@ fz_layout_html(fz_context *ctx, fz_html *box, float w, float h, float em)
 	layout_block(ctx, box, &page_box, em, h, 0);
 }
 
+typedef struct
+{
+	uint16_t *buffer;
+	size_t max;
+	size_t len;
+} uni_buf;
+
+typedef struct
+{
+	fz_context *ctx;
+	fz_pool *pool;
+	fz_html_flow *flow;
+	uni_buf *buffer;
+} bidi_data;
+
+static size_t utf8len(const char *text)
+{
+	size_t len = 0;
+
+	while (*text)
+	{
+		int rune;
+		text += fz_chartorune(&rune, text);
+		len++;
+	}
+	return len;
+}
+
+static void newFragCb(const uint16_t *fragment,
+			size_t fragmentLen,
+			int rightToLeft,
+			uint16_t mirror,
+			void *arg)
+{
+	bidi_data *data = (bidi_data *)arg;
+	size_t fragmentOffset = fragment - data->buffer->buffer;
+	int charDirR2L = rightToLeft;
+
+	if((fragmentOffset != 0) &&
+	   Bidi_isEuropeanNumber(fragment, fragmentLen))
+	{
+		/* fragment contains digits only */
+		charDirR2L = 0;
+	}
+
+	/* We are guaranteed that fragmentOffset will be at the beginning
+	 * of flow. */
+	while (fragmentLen > 0)
+	{
+		size_t len;
+
+		if (data->flow->type == FLOW_GLUE)
+		{
+			len = 1;
+		}
+		else
+		{
+			/* Must be text */
+			len = utf8len(data->flow->text);
+			if (len > fragmentLen)
+			{
+				/* We need to split this flow box */
+				(void)split_flow(data->ctx, data->pool, data->flow, fragmentLen);
+				len = utf8len(data->flow->text);
+			}
+		}
+
+		/* This flow box is entirely contained within this fragment. */
+		data->flow->block_r2l = rightToLeft;
+		data->flow->char_r2l = charDirR2L;
+		data->flow = data->flow->next;
+		fragmentOffset += len;
+		fragmentLen -= len;
+	}
+}
+
+static void
+detect_flow_directionality(fz_context *ctx, fz_pool *pool, uni_buf *buffer, fz_html_flow *flow)
+{
+	fz_html_flow *end = flow;
+	const char *text;
+	bidi_data data;
+	Bidi_Direction baseDir = -1;
+
+	/* Stage 1: Gather the text from the flow up into a single buffer */
+	buffer->len = 0;
+	while (end)
+	{
+		size_t len;
+		int broken = 0;
+
+		switch (end->type)
+		{
+		case FLOW_WORD:
+			len = utf8len(end->text);
+			text = end->text;
+			break;
+		case FLOW_GLUE:
+			len = 1;
+			text = " ";
+			break;
+		case FLOW_BREAK:
+		case FLOW_IMAGE:
+			broken = 1;
+			break;
+		}
+
+		if (broken)
+			break;
+
+		/* Make sure the buffer is large enough */
+		if (buffer->len + len > buffer->max)
+		{
+			size_t newmax = buffer->max * 2;
+			if (newmax == 0)
+				newmax = 128; /* Sensible small default */
+			buffer->buffer = fz_resize_array(ctx, buffer->buffer, newmax, sizeof(uint16_t));
+			buffer->max = newmax;
+		}
+
+		/* Expand the utf8 text into Unicode and store it in the buffer */
+		while (*text)
+		{
+			int rune;
+			text += fz_chartorune(&rune, text);
+			buffer->buffer[buffer->len++] = (uint16_t)rune;
+		}
+
+		end = end->next;
+	}
+
+	/* Detect directionality for the buffer */
+	data.ctx = ctx;
+	data.pool = pool;
+	data.flow = flow;
+	data.buffer = buffer;
+	Bidi_fragmentText(ctx,
+			buffer->buffer,
+			buffer->len,
+			&baseDir,
+			newFragCb, &data,
+			0 /* Flags */);
+}
+
+static void
+detect_box_directionality(fz_context *ctx, fz_pool *pool, uni_buf *buffer, fz_html *box)
+{
+	while (box)
+	{
+		if (box->flow_head)
+		{
+			detect_flow_directionality(ctx, pool, buffer, box->flow_head);
+		}
+		detect_box_directionality(ctx, pool, buffer, box->down);
+		box = box->next;
+	}
+}
+
+static void
+detect_directionality(fz_context *ctx, fz_pool *pool, fz_html *box)
+{
+	uni_buf buffer = { NULL };
+
+	detect_box_directionality(ctx, pool, &buffer, box);
+}
+
 fz_html *
 fz_parse_html(fz_context *ctx, fz_html_font_set *set, fz_archive *zip, const char *base_uri, fz_buffer *buf, const char *user_css)
 {
@@ -1380,5 +1573,7 @@ fz_parse_html(fz_context *ctx, fz_html_font_set *set, fz_archive *zip, const cha
 	fz_drop_css(ctx, css);
 	fz_drop_xml(ctx, xml);
 
+	detect_directionality(ctx, pool, box);
+
 	return box;
 }