Improve pagination.

Pagination was broken in horizontal mode before, and in general tried to
render too many results (leading to a cut-off last result). This commit
fixes both of those, with the minor caveat that you can no longer scroll
straight to the last result.

5 files changed, 161 insertions, 76 deletions

diff --git a/README.md b/README.md
index b2d8b0b..64cde1b 100644
--- a/README.md
+++ b/README.md
@@ -154,6 +154,12 @@ In roughly descending order, the most important options for performance are:
   the first frame). Again, on battery power on my laptop, drawing a fullscreen
   window (2880px × 1800px) takes ~20ms on the first frame, whereas a dmenu-like
   ribbon (2880px × 60px) takes ~1ms.
+  
+* `--num-results` - By default, tofi auto-detects how many results will fit in
+  the window. This is quite tricky when `--horizontal=true` is passed, and
+  leads to a few ms slowdown (only in this case). Setting a fixed number of
+  results will speed this up, but since this likely only applies to dmenu-like
+  themes (which are already very quick) it's probably not worth setting this.
 
 * `--hint-font` - Getting really into it now, one of the remaining slow points
   is hinting fonts. For the dmenu theme on battery power on my laptop, with a
diff --git a/src/entry.h b/src/entry.h
index 5ee4cd6..45865af 100644
--- a/src/entry.h
+++ b/src/entry.h
@@ -34,7 +34,7 @@ struct entry {
 	uint32_t input_mb_length;
 
 	uint32_t selection;
-	uint32_t page;
+	uint32_t first_result;
 	struct string_vec results;
 	struct string_vec commands;
 	struct desktop_vec apps;
@@ -51,6 +51,7 @@ struct entry {
 	bool horizontal;
 	uint32_t num_results;
 	uint32_t num_results_drawn;
+	uint32_t last_num_results_drawn;
 	int32_t result_spacing;
 	uint32_t font_size;
 	char font_name[MAX_FONT_NAME_LENGTH];
diff --git a/src/entry_backend/harfbuzz.c b/src/entry_backend/harfbuzz.c
index 45d5961..946bca3 100644
--- a/src/entry_backend/harfbuzz.c
+++ b/src/entry_backend/harfbuzz.c
@@ -26,6 +26,9 @@ const struct {
 #undef MAX
 #define MAX(a, b) ((a) > (b) ? (a) : (b))
 
+#undef MIN
+#define MIN(a, b) ((a) < (b) ? (a) : (b))
+
 static const char *get_ft_error_string(int err_code)
 {
 	for (size_t i = 0; i < N_ELEM(ft_errors); i++) {
@@ -185,6 +188,23 @@ void entry_backend_harfbuzz_destroy(struct entry *entry)
 	FT_Done_FreeType(entry->harfbuzz.ft_library);
 }
 
+static bool size_overflows(struct entry *entry, uint32_t width, uint32_t height)
+{
+	cairo_t *cr = entry->cairo[entry->index].cr;
+	cairo_matrix_t mat;
+	cairo_get_matrix(cr, &mat);
+	if (entry->horizontal) {
+		if (mat.x0 + width > entry->clip_x + entry->clip_width) {
+			return true;
+		}
+	} else {
+		if (mat.y0 + height > entry->clip_y + entry->clip_height) {
+			return true;
+		}
+	}
+	return false;
+}
+
 void entry_backend_harfbuzz_update(struct entry *entry)
 {
 	cairo_t *cr = entry->cairo[entry->index].cr;
@@ -215,35 +235,30 @@ void entry_backend_harfbuzz_update(struct entry *entry)
 	cairo_font_extents_t font_extents;
 	cairo_font_extents(cr, &font_extents);
 
-	cairo_matrix_t mat;
+	uint32_t num_results;
+	if (entry->num_results == 0) {
+		num_results = entry->results.count;
+	} else {
+		num_results = MIN(entry->num_results, entry->results.count);
+	}
 	/* Render our results */
-	for (size_t i = 0; i < entry->results.count; i++) {
+	size_t i;
+	for (i = 0; i < num_results; i++) {
 		if (entry->horizontal) {
 			cairo_translate(cr, width + entry->result_spacing, 0);
 		} else {
 			cairo_translate(cr, 0, font_extents.height + entry->result_spacing);
 		}
 		if (entry->num_results == 0) {
-			cairo_get_matrix(cr, &mat);
-			if (entry->horizontal) {
-				if (mat.x0 > entry->clip_x + entry->clip_width) {
-					entry->num_results_drawn = i;
-					log_debug("Drew %zu results.\n", i);
-					break;
-				}
-			} else {
-				if (mat.y0 > entry->clip_y + entry->clip_height) {
-					entry->num_results_drawn = i;
-					log_debug("Drew %zu results.\n", i);
-					break;
-				}
+			if (size_overflows(entry, 0, 0)) {
+				break;
 			}
 		} else if (i >= entry->num_results) {
 			break;
 		}
 
 
-		size_t index = i + entry->num_results * entry->page;
+		size_t index = i + entry->first_result;
 		/*
 		 * We may be on the last page, which could have fewer results
 		 * than expected, so check and break if necessary.
@@ -259,7 +274,48 @@ void entry_backend_harfbuzz_update(struct entry *entry)
 			setup_hb_buffer(buffer);
 			hb_buffer_add_utf8(buffer, result, -1, 0, -1);
 			hb_shape(entry->harfbuzz.hb_font, buffer, NULL, 0);
-			width = render_hb_buffer(cr, buffer);
+
+			if (entry->num_results > 0) {
+				/*
+				 * We're not auto-detecting how many results we
+				 * can fit, so just render the text.
+				 */
+				width = render_hb_buffer(cr, buffer);
+			} else if (!entry->horizontal) {
+				/*
+				 * The height of the text doesn't change, so
+				 * we don't need to re-measure it each time.
+				 */
+				if (size_overflows(entry, 0, font_extents.height)) {
+					entry->num_results_drawn = i;
+					break;
+				} else {
+					width = render_hb_buffer(cr, buffer);
+				}
+			} else {
+				/*
+				 * The difficult case: we're auto-detecting how
+				 * many results to draw, but we can't know
+				 * whether this results will fit without
+				 * drawing it! To solve this, draw to a
+				 * temporary group, measure that, then copy it
+				 * to the main canvas only if it will fit.
+				 */
+				cairo_push_group(cr);
+				width = render_hb_buffer(cr, buffer);
+				cairo_pattern_t *group = cairo_pop_group(cr);
+				if (size_overflows(entry, width, 0)) {
+					entry->num_results_drawn = i;
+					cairo_pattern_destroy(group);
+					break;
+				} else {
+					cairo_save(cr);
+					cairo_set_source(cr, group);
+					cairo_paint(cr);
+					cairo_restore(cr);
+					cairo_pattern_destroy(group);
+				}
+			}
 		} else {
 			/*
 			 * For the selected result, there's a bit more to do.
@@ -277,6 +333,10 @@ void entry_backend_harfbuzz_update(struct entry *entry)
 			 * portion of text - this is achieved simply by
 			 * splitting the text into prematch, match and
 			 * postmatch chunks, and drawing each separately.
+			 *
+			 * N.B. The size_overflows check isn't necessary here,
+			 * as it's currently not possible for the selection to
+			 * do so.
 			 */
 			size_t prematch_len;
 			char *prematch = xstrdup(result);
@@ -353,6 +413,8 @@ void entry_backend_harfbuzz_update(struct entry *entry)
 			cairo_set_source_rgba(cr, color.r, color.g, color.b, color.a);
 		}
 	}
+	entry->num_results_drawn = i;
+	log_debug("Drew %zu results.\n", i);
 
 	cairo_restore(cr);
 }
diff --git a/src/entry_backend/pango.c b/src/entry_backend/pango.c
index 41d8301..575bba2 100644
--- a/src/entry_backend/pango.c
+++ b/src/entry_backend/pango.c
@@ -9,6 +9,9 @@
 #undef MAX
 #define MAX(a, b) ((a) > (b) ? (a) : (b))
 
+#undef MIN
+#define MIN(a, b) ((a) < (b) ? (a) : (b))
+
 void entry_backend_pango_init(struct entry *entry, uint32_t *width, uint32_t *height)
 {
 	cairo_t *cr = entry->cairo[0].cr;
@@ -37,6 +40,23 @@ void entry_backend_pango_destroy(struct entry *entry)
 	g_object_unref(entry->pango.context);
 }
 
+static bool size_overflows(struct entry *entry, uint32_t width, uint32_t height)
+{
+	cairo_t *cr = entry->cairo[entry->index].cr;
+	cairo_matrix_t mat;
+	cairo_get_matrix(cr, &mat);
+	if (entry->horizontal) {
+		if (mat.x0 + width > entry->clip_x + entry->clip_width) {
+			return true;
+		}
+	} else {
+		if (mat.y0 + height > entry->clip_y + entry->clip_height) {
+			return true;
+		}
+	}
+	return false;
+}
+
 void entry_backend_pango_update(struct entry *entry)
 {
 	cairo_t *cr = entry->cairo[entry->index].cr;
@@ -64,33 +84,28 @@ void entry_backend_pango_update(struct entry *entry)
 	pango_layout_get_size(layout, &width, &height);
 	width = MAX(width, (int)entry->input_width * PANGO_SCALE);
 
-	cairo_matrix_t mat;
+	uint32_t num_results;
+	if (entry->num_results == 0) {
+		num_results = entry->results.count;
+	} else {
+		num_results = MIN(entry->num_results, entry->results.count);
+	}
 	/* Render our results */
-	for (size_t i = 0; i < entry->results.count; i++) {
+	size_t i;
+	for (i = 0; i < num_results; i++) {
 		if (entry->horizontal) {
 			cairo_translate(cr, (int)(width / PANGO_SCALE) + entry->result_spacing, 0);
 		} else {
 			cairo_translate(cr, 0, (int)(height / PANGO_SCALE) + entry->result_spacing);
 		}
 		if (entry->num_results == 0) {
-			cairo_get_matrix(cr, &mat);
-			if (entry->horizontal) {
-				if (mat.x0 > entry->clip_x + entry->clip_width) {
-					entry->num_results_drawn = i;
-					log_debug("Drew %zu results.\n", i);
-					break;
-				}
-			} else {
-				if (mat.y0 > entry->clip_y + entry->clip_height) {
-					entry->num_results_drawn = i;
-					log_debug("Drew %zu results.\n", i);
-					break;
-				}
+			if (size_overflows(entry, 0, 0)) {
+				break;
 			}
 		} else if (i >= entry->num_results) {
 			break;
 		}
-		size_t index = i + entry->num_results * entry->page;
+		size_t index = i + entry->first_result;
 		/*
 		 * We may be on the last page, which could have fewer results
 		 * than expected, so check and break if necessary.
@@ -108,8 +123,35 @@ void entry_backend_pango_update(struct entry *entry)
 		if (i != entry->selection) {
 			pango_layout_set_text(layout, str, -1);
 			pango_cairo_update_layout(cr, layout);
-			pango_cairo_show_layout(cr, layout);
-			pango_layout_get_size(layout, &width, &height);
+
+			if (entry->num_results > 0) {
+				pango_cairo_show_layout(cr, layout);
+				pango_layout_get_size(layout, &width, &height);
+			} else if (!entry->horizontal) {
+				if (size_overflows(entry, 0, height / PANGO_SCALE)) {
+					entry->num_results_drawn = i;
+					break;
+				} else {
+					pango_cairo_show_layout(cr, layout);
+					pango_layout_get_size(layout, &width, &height);
+				}
+			} else {
+				cairo_push_group(cr);
+				pango_cairo_show_layout(cr, layout);
+				pango_layout_get_size(layout, &width, &height);
+				cairo_pattern_t *group = cairo_pop_group(cr);
+				if (size_overflows(entry, width / PANGO_SCALE, 0)) {
+					entry->num_results_drawn = i;
+					cairo_pattern_destroy(group);
+					break;
+				} else {
+					cairo_save(cr);
+					cairo_set_source(cr, group);
+					cairo_paint(cr);
+					cairo_restore(cr);
+					cairo_pattern_destroy(group);
+				}
+			}
 		} else {
 			ssize_t prematch_len = -1;
 			size_t match_len = entry->input_mb_length;
@@ -170,6 +212,8 @@ void entry_backend_pango_update(struct entry *entry)
 			cairo_set_source_rgba(cr, color.r, color.g, color.b, color.a);
 		}
 	}
+	entry->num_results_drawn = i;
+	log_debug("Drew %zu results.\n", i);
 
 	cairo_restore(cr);
 }
diff --git a/src/main.c b/src/main.c
index be13a28..805f364 100644
--- a/src/main.c
+++ b/src/main.c
@@ -209,27 +209,7 @@ static void handle_keypress(struct tofi *tofi, xkb_keycode_t keycode)
 		return;
 	}
 
-	/*
-	 * If 0 was passed to num-results, use the number we've managed to fit
-	 * in the window from now on.
-	 */
-	if (entry->num_results == 0) {
-		entry->num_results = entry->num_results_drawn;
-	}
-	/* Number of pages of results available. */
-	uint32_t n_pages = ceil(entry->results.count / (double)entry->num_results);
-	uint32_t page_size;
-
-	/* There may be fewer than num-results entries on the last page. */
-	if (entry->page == n_pages - 1) {
-		page_size = entry->results.count % entry->num_results;
-		if (page_size == 0) {
-			page_size = entry->num_results;
-		}
-	} else {
-		page_size = entry->num_results;
-	}
-	uint32_t nsel = MAX(MIN(page_size, entry->results.count), 1);
+	uint32_t nsel = MAX(MIN(entry->num_results_drawn, entry->results.count), 1);
 	if (sym == XKB_KEY_Up || sym == XKB_KEY_Left
 			|| (sym == XKB_KEY_k
 				&& xkb_state_mod_name_is_active(
@@ -241,21 +221,12 @@ static void handle_keypress(struct tofi *tofi, xkb_keycode_t keycode)
 		if (entry->selection > 0) {
 			entry->selection--;
 		} else {
-			if (entry->page > 0) {
-				entry->page--;
-				entry->selection = entry->num_results - 1;
-			} else {
-				/*
-				 * We're about to wrap around to the last
-				 * result, so we need to calculate the size of
-				 * the last page.
-				 */
-				entry->page = n_pages - 1;
-				page_size = entry->results.count % entry->num_results;
-				if (page_size == 0) {
-					page_size = entry->num_results;
-				}
-				entry->selection = page_size - 1;
+			if (entry->first_result > nsel) {
+				entry->first_result -= entry->last_num_results_drawn;
+				entry->selection = entry->last_num_results_drawn - 1;
+			} else if (entry->first_result > 0) {
+				entry->selection = entry->first_result - 1;
+				entry->first_result = 0;
 			}
 		}
 	} else if (sym == XKB_KEY_Down || sym == XKB_KEY_Right || sym == XKB_KEY_Tab
@@ -269,12 +240,13 @@ static void handle_keypress(struct tofi *tofi, xkb_keycode_t keycode)
 		entry->selection++;
 		if (entry->selection >= nsel) {
 			entry->selection -= nsel;
-			entry->page++;
-			entry->page %= n_pages;
+			entry->first_result += nsel;
+			entry->first_result %= entry->results.count;
+			entry->last_num_results_drawn = entry->num_results_drawn;
 		}
 	} else {
 		entry->selection = 0;
-		entry->page = 0;
+		entry->first_result = 0;
 	}
 	entry_update(&tofi->window.entry);
 	tofi->window.surface.redraw = true;
@@ -937,7 +909,7 @@ static void parse_args(struct tofi *tofi, int argc, char *argv[])
 static void do_submit(struct tofi *tofi)
 {
 	struct entry *entry = &tofi->window.entry;
-	uint32_t selection = entry->selection + entry->num_results * entry->page;
+	uint32_t selection = entry->selection + entry->first_result;
 	char *res = entry->results.buf[selection].string;
 	if (entry->drun) {
 		/*