1/* $OpenBSD: hyperlinks.c,v 1.3 2023/06/30 13:19:32 nicm Exp $ */
2
3/*
4 * Copyright (c) 2021 Will <author@will.party>
5 * Copyright (c) 2022 Jeff Chiang <pobomp@gmail.com>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER
16 * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
17 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20#include <sys/types.h>
21
22#include <stdlib.h>
23#include <string.h>
24#include <vis.h>
25
26#include "tmux.h"
27
28/*
29 * OSC 8 hyperlinks, described at:
30 *
31 *     https://gist.github.com/egmontkob/eb114294efbcd5adb1944c9f3cb5feda
32 *
33 * Each hyperlink and ID combination is assigned a number ("inner" in this
34 * file) which is stored in an extended grid cell and maps into a tree here.
35 *
36 * Each URI has one inner number and one external ID (which tmux uses to send
37 * the hyperlink to the terminal) and one internal ID (which is received from
38 * the sending application inside tmux).
39 *
40 * Anonymous hyperlinks are each unique and are not reused even if they have
41 * the same URI (terminals will not want to tie them together).
42 */
43
44#define MAX_HYPERLINKS 5000
45
46static long long hyperlinks_next_external_id = 1;
47static u_int global_hyperlinks_count;
48
49struct hyperlinks_uri {
50	struct hyperlinks	*tree;
51
52	u_int			 inner;
53	const char		*internal_id;
54	const char		*external_id;
55	const char		*uri;
56
57	TAILQ_ENTRY(hyperlinks_uri) list_entry;
58	RB_ENTRY(hyperlinks_uri)    by_inner_entry;
59	RB_ENTRY(hyperlinks_uri)    by_uri_entry; /* by internal ID and URI */
60};
61RB_HEAD(hyperlinks_by_uri_tree, hyperlinks_uri);
62RB_HEAD(hyperlinks_by_inner_tree, hyperlinks_uri);
63
64TAILQ_HEAD(hyperlinks_list, hyperlinks_uri);
65static struct hyperlinks_list global_hyperlinks =
66    TAILQ_HEAD_INITIALIZER(global_hyperlinks);
67
68struct hyperlinks {
69	u_int				next_inner;
70	struct hyperlinks_by_inner_tree	by_inner;
71	struct hyperlinks_by_uri_tree	by_uri;
72};
73
74static int
75hyperlinks_by_uri_cmp(struct hyperlinks_uri *left, struct hyperlinks_uri *right)
76{
77	int	r;
78
79	if (*left->internal_id == '\0' || *right->internal_id == '\0') {
80		/*
81		 * If both URIs are anonymous, use the inner for comparison so
82		 * that they do not match even if the URI is the same - each
83		 * anonymous URI should be unique.
84		 */
85		if (*left->internal_id != '\0')
86			return (-1);
87		if (*right->internal_id != '\0')
88			return (1);
89		return (left->inner - right->inner);
90	}
91
92	r = strcmp(left->internal_id, right->internal_id);
93	if (r != 0)
94		return (r);
95	return (strcmp(left->uri, right->uri));
96}
97RB_PROTOTYPE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
98    hyperlinks_by_uri_cmp);
99RB_GENERATE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
100    hyperlinks_by_uri_cmp);
101
102static int
103hyperlinks_by_inner_cmp(struct hyperlinks_uri *left,
104    struct hyperlinks_uri *right)
105{
106	return (left->inner - right->inner);
107}
108RB_PROTOTYPE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
109    hyperlinks_by_inner_cmp);
110RB_GENERATE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
111    hyperlinks_by_inner_cmp);
112
113/* Remove a hyperlink. */
114static void
115hyperlinks_remove(struct hyperlinks_uri *hlu)
116{
117	struct hyperlinks	*hl = hlu->tree;
118
119	TAILQ_REMOVE(&global_hyperlinks, hlu, list_entry);
120	global_hyperlinks_count--;
121
122	RB_REMOVE(hyperlinks_by_inner_tree, &hl->by_inner, hlu);
123	RB_REMOVE(hyperlinks_by_uri_tree, &hl->by_uri, hlu);
124
125	free((void *)hlu->internal_id);
126	free((void *)hlu->external_id);
127	free((void *)hlu->uri);
128	free(hlu);
129}
130
131/* Store a new hyperlink or return if it already exists. */
132u_int
133hyperlinks_put(struct hyperlinks *hl, const char *uri_in,
134    const char *internal_id_in)
135{
136	struct hyperlinks_uri	 find, *hlu;
137	char			*uri, *internal_id, *external_id;
138
139	/*
140	 * Anonymous URI are stored with an empty internal ID and the tree
141	 * comparator will make sure they never match each other (so each
142	 * anonymous URI is unique).
143	 */
144	if (internal_id_in == NULL)
145		internal_id_in = "";
146
147	utf8_stravis(&uri, uri_in, VIS_OCTAL|VIS_CSTYLE);
148	utf8_stravis(&internal_id, internal_id_in, VIS_OCTAL|VIS_CSTYLE);
149
150	if (*internal_id_in != '\0') {
151		find.uri = uri;
152		find.internal_id = internal_id;
153
154		hlu = RB_FIND(hyperlinks_by_uri_tree, &hl->by_uri, &find);
155		if (hlu != NULL) {
156			free (uri);
157			free (internal_id);
158			return (hlu->inner);
159		}
160	}
161	xasprintf(&external_id, "tmux%llX", hyperlinks_next_external_id++);
162
163	hlu = xcalloc(1, sizeof *hlu);
164	hlu->inner = hl->next_inner++;
165	hlu->internal_id = internal_id;
166	hlu->external_id = external_id;
167	hlu->uri = uri;
168	hlu->tree = hl;
169	RB_INSERT(hyperlinks_by_uri_tree, &hl->by_uri, hlu);
170	RB_INSERT(hyperlinks_by_inner_tree, &hl->by_inner, hlu);
171
172	TAILQ_INSERT_TAIL(&global_hyperlinks, hlu, list_entry);
173	if (++global_hyperlinks_count == MAX_HYPERLINKS)
174		hyperlinks_remove(TAILQ_FIRST(&global_hyperlinks));
175
176	return (hlu->inner);
177}
178
179/* Get hyperlink by inner number. */
180int
181hyperlinks_get(struct hyperlinks *hl, u_int inner, const char **uri_out,
182    const char **internal_id_out, const char **external_id_out)
183{
184	struct hyperlinks_uri	find, *hlu;
185
186	find.inner = inner;
187
188	hlu = RB_FIND(hyperlinks_by_inner_tree, &hl->by_inner, &find);
189	if (hlu == NULL)
190		return (0);
191	if (internal_id_out != NULL)
192		*internal_id_out = hlu->internal_id;
193	if (external_id_out != NULL)
194		*external_id_out = hlu->external_id;
195	*uri_out = hlu->uri;
196	return (1);
197}
198
199/* Initialize hyperlink set. */
200struct hyperlinks *
201hyperlinks_init(void)
202{
203	struct hyperlinks	*hl;
204
205	hl = xcalloc(1, sizeof *hl);
206	hl->next_inner = 1;
207	RB_INIT(&hl->by_uri);
208	RB_INIT(&hl->by_inner);
209	return (hl);
210}
211
212/* Free all hyperlinks but not the set itself. */
213void
214hyperlinks_reset(struct hyperlinks *hl)
215{
216	struct hyperlinks_uri	*hlu, *hlu1;
217
218	RB_FOREACH_SAFE(hlu, hyperlinks_by_inner_tree, &hl->by_inner, hlu1)
219		hyperlinks_remove(hlu);
220}
221
222/* Free hyperlink set. */
223void
224hyperlinks_free(struct hyperlinks *hl)
225{
226	hyperlinks_reset(hl);
227	free(hl);
228}
229