Make positions hidden by overlays range-based rather than character-based,

from Anindya Mukherjee.

6 files changed, 202 insertions, 79 deletions

diff --git a/usr.bin/tmux/menu.c b/usr.bin/tmux/menu.c
index 0a1fa0da60e..5eb90534d9e 100644
--- a/usr.bin/tmux/menu.c
+++ b/usr.bin/tmux/menu.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: menu.c,v 1.37 2021/09/09 19:37:17 nicm Exp $ */
+/* $OpenBSD: menu.c,v 1.38 2021/10/11 13:27:50 nicm Exp $ */
 
 /*
  * Copyright (c) 2019 Nicholas Marriott <nicholas.marriott@gmail.com>
@@ -140,17 +140,16 @@ menu_mode_cb(__unused struct client *c, void *data, __unused u_int *cx,
 	return (&md->s);
 }
 
-int
-menu_check_cb(__unused struct client *c, void *data, u_int px, u_int py)
+/* Return parts of the input range which are not obstructed by the menu. */
+void
+menu_check_cb(__unused struct client *c, void *data, u_int px, u_int py,
+    u_int nx, struct overlay_ranges *r)
 {
 	struct menu_data	*md = data;
 	struct menu		*menu = md->menu;
 
-	if (px < md->px || px > md->px + menu->width + 3)
-		return (1);
-	if (py < md->py || py > md->py + menu->count + 1)
-		return (1);
-	return (0);
+	server_client_overlay_range(md->px, md->py, menu->width + 4,
+	    menu->count + 2, px, py, nx, r);
 }
 
 void
diff --git a/usr.bin/tmux/popup.c b/usr.bin/tmux/popup.c
index 76f9e4c8d99..0f035a2443b 100644
--- a/usr.bin/tmux/popup.c
+++ b/usr.bin/tmux/popup.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: popup.c,v 1.35 2021/10/11 10:55:30 nicm Exp $ */
+/* $OpenBSD: popup.c,v 1.36 2021/10/11 13:27:50 nicm Exp $ */
 
 /*
  * Copyright (c) 2020 Nicholas Marriott <nicholas.marriott@gmail.com>
@@ -157,18 +157,49 @@ popup_mode_cb(__unused struct client *c, void *data, u_int *cx, u_int *cy)
 	return (&pd->s);
 }
 
-static int
-popup_check_cb(struct client *c, void *data, u_int px, u_int py)
+/* Return parts of the input range which are not obstructed by the popup. */
+static void
+popup_check_cb(struct client* c, void *data, u_int px, u_int py, u_int nx,
+    struct overlay_ranges *r)
 {
 	struct popup_data	*pd = data;
+	struct overlay_ranges	 or[2];
+	u_int			 i, j, k = 0;
 
-	if (pd->md != NULL && menu_check_cb(c, pd->md, px, py) == 0)
-		return (0);
-	if (px < pd->px || px > pd->px + pd->sx - 1)
-		return (1);
-	if (py < pd->py || py > pd->py + pd->sy - 1)
-		return (1);
-	return (0);
+	if (pd->md != NULL) {
+		/* Check each returned range for the menu against the popup. */
+		menu_check_cb(c, pd->md, px, py, nx, r);
+		for (i = 0; i < 2; i++) {
+			server_client_overlay_range(pd->px, pd->py, pd->sx,
+			    pd->sy, r->px[i], py, r->nx[i], &or[i]);
+		}
+
+		/*
+		 * or has up to OVERLAY_MAX_RANGES non-overlapping ranges,
+		 * ordered from left to right. Collect them in the output.
+		 */
+		for (i = 0; i < 2; i++) {
+			/* Each or[i] only has 2 ranges. */
+			for (j = 0; j < 2; j++) {
+				if (or[i].nx[j] > 0) {
+					r->px[k] = or[i].px[j];
+					r->nx[k] = or[i].nx[j];
+					k++;
+				}
+			}
+		}
+
+		/* Zero remaining ranges if any. */
+		for (i = k; i < OVERLAY_MAX_RANGES; i++) {
+			r->px[i] = 0;
+			r->nx[i] = 0;
+		}
+
+		return;
+	}
+
+	server_client_overlay_range(pd->px, pd->py, pd->sx, pd->sy, px, py, nx,
+	    r);
 }
 
 static void
diff --git a/usr.bin/tmux/screen-redraw.c b/usr.bin/tmux/screen-redraw.c
index 2273edfd25f..2608d112d26 100644
--- a/usr.bin/tmux/screen-redraw.c
+++ b/usr.bin/tmux/screen-redraw.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: screen-redraw.c,v 1.88 2021/08/13 18:54:54 nicm Exp $ */
+/* $OpenBSD: screen-redraw.c,v 1.89 2021/10/11 13:27:50 nicm Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicholas.marriott@gmail.com>
@@ -685,14 +685,17 @@ screen_redraw_draw_borders_cell(struct screen_redraw_ctx *ctx, u_int i, u_int j)
 	struct tty		*tty = &c->tty;
 	struct format_tree	*ft;
 	struct window_pane	*wp;
-	u_int			 cell_type, x = ctx->ox + i, y = ctx->oy + j;
-	int			 pane_status = ctx->pane_status, isolates;
 	struct grid_cell	 gc;
 	const struct grid_cell	*tmp;
+	struct overlay_ranges	 r;
+	u_int			 cell_type, x = ctx->ox + i, y = ctx->oy + j;
+	int			 pane_status = ctx->pane_status, isolates;
 
-	if (c->overlay_check != NULL &&
-	    !c->overlay_check(c, c->overlay_data, x, y))
-		return;
+	if (c->overlay_check != NULL) {
+		c->overlay_check(c, c->overlay_data, x, y, 1, &r);
+		if (r.nx[0] + r.nx[1] == 0)
+			return;
+	}
 
 	cell_type = screen_redraw_check_cell(c, x, y, pane_status, &wp);
 	if (cell_type == CELL_INSIDE)
diff --git a/usr.bin/tmux/server-client.c b/usr.bin/tmux/server-client.c
index 0d1f3baf2e8..8e372fd8d18 100644
--- a/usr.bin/tmux/server-client.c
+++ b/usr.bin/tmux/server-client.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: server-client.c,v 1.387 2021/09/27 19:12:00 nicm Exp $ */
+/* $OpenBSD: server-client.c,v 1.388 2021/10/11 13:27:50 nicm Exp $ */
 
 /*
  * Copyright (c) 2009 Nicholas Marriott <nicholas.marriott@gmail.com>
@@ -147,6 +147,54 @@ server_client_clear_overlay(struct client *c)
 	server_redraw_client(c);
 }
 
+/*
+ * Given overlay position and dimensions, return parts of the input range which
+ * are visible.
+ */
+void
+server_client_overlay_range(u_int x, u_int y, u_int sx, u_int sy, u_int px,
+    u_int py, u_int nx, struct overlay_ranges *r)
+{
+	u_int	ox, onx;
+
+	/* Return up to 2 ranges. */
+	r->px[2] = 0;
+	r->nx[2] = 0;
+
+	/* Trivial case of no overlap in the y direction. */
+	if (py < y || py > y + sy - 1) {
+		r->px[0] = px;
+		r->nx[0] = nx;
+		r->px[1] = 0;
+		r->nx[1] = 0;
+		return;
+	}
+
+	/* Visible bit to the left of the popup. */
+	if (px < x) {
+		r->px[0] = px;
+		r->nx[0] = x - px;
+		if (r->nx[0] > nx)
+			r->nx[0] = nx;
+	} else {
+		r->px[0] = 0;
+		r->nx[0] = 0;
+	}
+
+	/* Visible bit to the right of the popup. */
+	ox = x + sx;
+	if (px > ox)
+		ox = px;
+	onx = px + nx;
+	if (onx > ox) {
+		r->px[1] = ox;
+		r->nx[1] = onx - ox;
+	} else {
+		r->px[1] = 0;
+		r->nx[1] = 0;
+	}
+}
+
 /* Check if this client is inside this server. */
 int
 server_client_check_nested(struct client *c)
diff --git a/usr.bin/tmux/tmux.h b/usr.bin/tmux/tmux.h
index 4a861f2e54c..bb329005151 100644
--- a/usr.bin/tmux/tmux.h
+++ b/usr.bin/tmux/tmux.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: tmux.h,v 1.1144 2021/10/11 10:55:30 nicm Exp $ */
+/* $OpenBSD: tmux.h,v 1.1145 2021/10/11 13:27:50 nicm Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicholas.marriott@gmail.com>
@@ -1567,10 +1567,18 @@ struct client_window {
 };
 RB_HEAD(client_windows, client_window);
 
+/* Visible areas not obstructed by overlays. */
+#define OVERLAY_MAX_RANGES 3
+struct overlay_ranges {
+	u_int	px[OVERLAY_MAX_RANGES];
+	u_int	nx[OVERLAY_MAX_RANGES];
+};
+
 /* Client connection. */
 typedef int (*prompt_input_cb)(struct client *, void *, const char *, int);
 typedef void (*prompt_free_cb)(void *);
-typedef int (*overlay_check_cb)(struct client *, void *, u_int, u_int);
+typedef void (*overlay_check_cb)(struct client*, void *, u_int, u_int, u_int,
+	    struct overlay_ranges *);
 typedef struct screen *(*overlay_mode_cb)(struct client *, void *, u_int *,
 	    u_int *);
 typedef void (*overlay_draw_cb)(struct client *, void *,
@@ -2462,6 +2470,8 @@ void	 server_client_set_overlay(struct client *, u_int, overlay_check_cb,
 	     overlay_mode_cb, overlay_draw_cb, overlay_key_cb,
 	     overlay_free_cb, overlay_resize_cb, void *);
 void	 server_client_clear_overlay(struct client *);
+void	 server_client_overlay_range(u_int, u_int, u_int, u_int, u_int, u_int,
+	     u_int, struct overlay_ranges *);
 void	 server_client_set_key_table(struct client *, const char *);
 const char *server_client_get_key_table(struct client *);
 int	 server_client_check_nested(struct client *);
@@ -3091,7 +3101,8 @@ int		 menu_display(struct menu *, int, struct cmdq_item *, u_int,
 		    u_int, struct client *, struct cmd_find_state *,
 		    menu_choice_cb, void *);
 struct screen	*menu_mode_cb(struct client *, void *, u_int *, u_int *);
-int		 menu_check_cb(struct client *, void *, u_int, u_int);
+void		 menu_check_cb(struct client *, void *, u_int, u_int, u_int,
+		    struct overlay_ranges *);
 void		 menu_draw_cb(struct client *, void *,
 		    struct screen_redraw_ctx *);
 void		 menu_free_cb(struct client *, void *);
diff --git a/usr.bin/tmux/tty.c b/usr.bin/tmux/tty.c
index 9426448acda..6a6b883d3e9 100644
--- a/usr.bin/tmux/tty.c
+++ b/usr.bin/tmux/tty.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: tty.c,v 1.405 2021/10/06 10:33:12 nicm Exp $ */
+/* $OpenBSD: tty.c,v 1.406 2021/10/11 13:27:50 nicm Exp $ */
 
 /*
  * Copyright (c) 2007 Nicholas Marriott <nicholas.marriott@gmail.com>
@@ -71,6 +71,8 @@ static void	tty_draw_pane(struct tty *, const struct tty_ctx *, u_int);
 static void	tty_default_attributes(struct tty *, const struct grid_cell *,
 		    struct colour_palette *, u_int);
 static int	tty_check_overlay(struct tty *, u_int, u_int);
+static void	tty_check_overlay_range(struct tty *, u_int, u_int, u_int,
+		    struct overlay_ranges *);
 
 #define tty_use_margin(tty) \
 	(tty->term->flags & TERM_DECSLRM)
@@ -1046,8 +1048,9 @@ static void
 tty_clear_line(struct tty *tty, const struct grid_cell *defaults, u_int py,
     u_int px, u_int nx, u_int bg)
 {
-	struct client	*c = tty->client;
-	u_int		 i;
+	struct client		*c = tty->client;
+	struct overlay_ranges	 r;
+	u_int			 i;
 
 	log_debug("%s: %s, %u at %u,%u", __func__, c->name, nx, px, py);
 
@@ -1083,18 +1086,13 @@ tty_clear_line(struct tty *tty, const struct grid_cell *defaults, u_int py,
 	 * Couldn't use an escape sequence, use spaces. Clear only the visible
 	 * bit if there is an overlay.
 	 */
-	for (i = 0; i < nx; i++) {
-		if (!tty_check_overlay(tty, px + i, py))
-			break;
-	}
-	tty_cursor(tty, px, py);
-	tty_repeat_space(tty, i);
-	for (; i < nx; i++) {
-		if (tty_check_overlay(tty, px + i, py))
-			break;
+	tty_check_overlay_range(tty, px, py, nx, &r);
+	for (i = 0; i < OVERLAY_MAX_RANGES; i++) {
+		if (r.nx[i] == 0)
+			continue;
+		tty_cursor(tty, r.px[i], py);
+		tty_repeat_space(tty, r.nx[i]);
 	}
-	tty_cursor(tty, px + i, py);
-	tty_repeat_space(tty, nx - i);
 }
 
 /* Clear a line, adjusting to visible part of pane. */
@@ -1306,14 +1304,44 @@ tty_check_codeset(struct tty *tty, const struct grid_cell *gc)
 	return (&new);
 }
 
+/*
+ * Check if a single character is obstructed by the overlay and return a
+ * boolean.
+ */
 static int
 tty_check_overlay(struct tty *tty, u_int px, u_int py)
 {
+	struct overlay_ranges	r;
+
+	/*
+	 * A unit width range will always return nx[2] == 0 from a check, even
+	 * with multiple overlays, so it's sufficient to check just the first
+	 * two entries.
+	 */
+	tty_check_overlay_range(tty, px, py, 1, &r);
+	if (r.nx[0] + r.nx[1] == 0)
+		return (0);
+	return (1);
+}
+
+/* Return parts of the input range which are visible. */
+static void
+tty_check_overlay_range(struct tty *tty, u_int px, u_int py, u_int nx,
+    struct overlay_ranges *r)
+{
 	struct client	*c = tty->client;
 
-	if (c->overlay_check == NULL)
-		return (1);
-	return (c->overlay_check(c, c->overlay_data, px, py));
+	if (c->overlay_check == NULL) {
+		r->px[0] = px;
+		r->nx[0] = nx;
+		r->px[1] = 0;
+		r->nx[1] = 0;
+		r->px[2] = 0;
+		r->nx[2] = 0;
+		return;
+	}
+
+	c->overlay_check(c, c->overlay_data, px, py, nx, r);
 }
 
 void
@@ -1326,11 +1354,12 @@ tty_draw_line(struct tty *tty, struct screen *s, u_int px, u_int py, u_int nx,
 	const struct grid_cell	*gcp;
 	struct grid_line	*gl;
 	struct client		*c = tty->client;
-	u_int			 i, j, ux, sx, width, hidden;
+	struct overlay_ranges	 r;
+	u_int			 i, j, ux, sx, width, hidden, eux, nxx;
+	u_int			 cellsize;
 	int			 flags, cleared = 0, wrapped = 0;
 	char			 buf[512];
 	size_t			 len;
-	u_int			 cellsize;
 
 	log_debug("%s: px=%u py=%u nx=%u atx=%u aty=%u", __func__,
 	    px, py, nx, atx, aty);
@@ -1430,29 +1459,31 @@ tty_draw_line(struct tty *tty, struct screen *s, u_int px, u_int py, u_int nx,
 		else
 			memcpy(&last, gcp, sizeof last);
 
+		tty_check_overlay_range(tty, atx + ux, aty, gcp->data.width,
+		    &r);
 		hidden = 0;
-		for (j = 0; j < gcp->data.width; j++) {
-			if (!tty_check_overlay(tty, atx + ux + j, aty))
-				hidden++;
-		}
+		for (j = 0; j < OVERLAY_MAX_RANGES; j++)
+			hidden += r.nx[j];
+		hidden = gcp->data.width - hidden;
 		if (hidden != 0 && hidden == gcp->data.width) {
 			if (~gcp->flags & GRID_FLAG_PADDING)
 				ux += gcp->data.width;
 		} else if (hidden != 0 || ux + gcp->data.width > nx) {
 			if (~gcp->flags & GRID_FLAG_PADDING) {
 				tty_attributes(tty, &last, defaults, palette);
-				tty_cursor(tty, atx + ux, aty);
-				for (j = 0; j < gcp->data.width; j++) {
-					if (ux > nx)
-						break;
-					if (tty_check_overlay(tty, atx + ux,
-					    aty))
-						tty_putc(tty, ' ');
-					else {
-						tty_cursor(tty, atx + ux + 1,
-						    aty);
+				for (j = 0; j < OVERLAY_MAX_RANGES; j++) {
+					if (r.nx[j] == 0)
+						continue;
+					/* Effective width drawn so far. */
+					eux = r.px[j] - atx;
+					if (eux < nx) {
+						tty_cursor(tty, r.px[j], aty);
+						nxx = nx - eux;
+						if (r.nx[j] > nxx)
+							r.nx[j] = nxx;
+						tty_repeat_space(tty, r.nx[j]);
+						ux = eux + r.nx[j];
 					}
-					ux++;
 				}
 			}
 		} else if (gcp->attr & GRID_ATTR_CHARSET) {
@@ -1926,7 +1957,8 @@ tty_cmd_cell(struct tty *tty, const struct tty_ctx *ctx)
 {
 	const struct grid_cell	*gcp = ctx->cell;
 	struct screen		*s = ctx->s;
-	u_int			 i, px, py;
+	struct overlay_ranges	 r;
+	u_int			 px, py, i, vis = 0;
 
 	px = ctx->xoff + ctx->ocx - ctx->wox;
 	py = ctx->yoff + ctx->ocy - ctx->woy;
@@ -1936,13 +1968,14 @@ tty_cmd_cell(struct tty *tty, const struct tty_ctx *ctx)
 
 	/* Handle partially obstructed wide characters. */
 	if (gcp->data.width > 1) {
-		for (i = 0; i < gcp->data.width; i++) {
-			if (!tty_check_overlay(tty, px + i, py)) {
-				tty_draw_line(tty, s, s->cx, s->cy,
+		tty_check_overlay_range(tty, px, py, gcp->data.width, &r);
+		for (i = 0; i < OVERLAY_MAX_RANGES; i++)
+			vis += r.nx[i];
+		if (vis < gcp->data.width) {
+			tty_draw_line(tty, s, s->cx, s->cy,
 				    gcp->data.width, px, py, &ctx->defaults,
 				    ctx->palette);
 				return;
-			}
 		}
 	}
 
@@ -1960,7 +1993,8 @@ tty_cmd_cell(struct tty *tty, const struct tty_ctx *ctx)
 void
 tty_cmd_cells(struct tty *tty, const struct tty_ctx *ctx)
 {
-	u_int	i, hide = 0;
+	struct overlay_ranges	r;
+	u_int			i, px;
 
 	if (!tty_is_visible(tty, ctx, ctx->ocx, ctx->ocy, ctx->num, 1))
 		return;
@@ -1985,18 +2019,15 @@ tty_cmd_cells(struct tty *tty, const struct tty_ctx *ctx)
 	tty_cursor_pane_unless_wrap(tty, ctx, ctx->ocx, ctx->ocy);
 
 	tty_attributes(tty, ctx->cell, &ctx->defaults, ctx->palette);
-	for (i = 0; i < ctx->num; i++) {
-		if (!tty_check_overlay(tty, tty->cx + i, tty->cy))
-			break;
-	}
-	tty_putn(tty, ctx->ptr, i, i);
-	for (; i < ctx->num; i++) {
-		if (tty_check_overlay(tty, tty->cx + hide, tty->cy))
-			break;
-		hide++;
+	px = tty->cx;
+	tty_check_overlay_range(tty, px, tty->cy, ctx->num, &r);
+	for (i = 0; i < OVERLAY_MAX_RANGES; i++) {
+		if (r.nx[i] == 0)
+			continue;
+		tty_cursor(tty, r.px[i], tty->cy);
+		tty_putn(tty, (char *)ctx->ptr + r.px[i] - px, r.nx[i],
+		    r.nx[i]);
 	}
-	tty_cursor(tty, tty->cx + hide, tty->cy);
-	tty_putn(tty, (char *)ctx->ptr + i, ctx->num - i, ctx->num - i);
 }
 
 void