1/* $OpenBSD$ */
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
25#include "tmux.h"
26
27/*
28 * OSC 8 hyperlinks, described at:
29 *
30 *     https://gist.github.com/egmontkob/eb114294efbcd5adb1944c9f3cb5feda
31 *
32 * Each hyperlink and ID combination is assigned a number ("inner" in this
33 * file) which is stored in an extended grid cell and maps into a tree here.
34 *
35 * Each URI has one inner number and one external ID (which tmux uses to send
36 * the hyperlink to the terminal) and one internal ID (which is received from
37 * the sending application inside tmux).
38 *
39 * Anonymous hyperlinks are each unique and are not reused even if they have
40 * the same URI (terminals will not want to tie them together).
41 */
42
43#define MAX_HYPERLINKS 5000
44
45static long long hyperlinks_next_external_id = 1;
46static u_int global_hyperlinks_count;
47
48struct hyperlinks_uri {
49	struct hyperlinks	*tree;
50
51	u_int			 inner;
52	const char		*internal_id;
53	const char		*external_id;
54	const char		*uri;
55
56	TAILQ_ENTRY(hyperlinks_uri) list_entry;
57	RB_ENTRY(hyperlinks_uri)    by_inner_entry;
58	RB_ENTRY(hyperlinks_uri)    by_uri_entry; /* by internal ID and URI */
59};
60RB_HEAD(hyperlinks_by_uri_tree, hyperlinks_uri);
61RB_HEAD(hyperlinks_by_inner_tree, hyperlinks_uri);
62
63TAILQ_HEAD(hyperlinks_list, hyperlinks_uri);
64static struct hyperlinks_list global_hyperlinks =
65    TAILQ_HEAD_INITIALIZER(global_hyperlinks);
66
67struct hyperlinks {
68	u_int				next_inner;
69	struct hyperlinks_by_inner_tree	by_inner;
70	struct hyperlinks_by_uri_tree	by_uri;
71};
72
73static int
74hyperlinks_by_uri_cmp(struct hyperlinks_uri *left, struct hyperlinks_uri *right)
75{
76	int	r;
77
78	if (*left->internal_id == '\0' || *right->internal_id == '\0') {
79		/*
80		 * If both URIs are anonymous, use the inner for comparison so
81		 * that they do not match even if the URI is the same - each
82		 * anonymous URI should be unique.
83		 */
84		if (*left->internal_id != '\0')
85			return (-1);
86		if (*right->internal_id != '\0')
87			return (1);
88		return (left->inner - right->inner);
89	}
90
91	r = strcmp(left->internal_id, right->internal_id);
92	if (r != 0)
93		return (r);
94	return (strcmp(left->uri, right->uri));
95}
96RB_PROTOTYPE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
97    hyperlinks_by_uri_cmp);
98RB_GENERATE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
99    hyperlinks_by_uri_cmp);
100
101static int
102hyperlinks_by_inner_cmp(struct hyperlinks_uri *left,
103    struct hyperlinks_uri *right)
104{
105	return (left->inner - right->inner);
106}
107RB_PROTOTYPE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
108    hyperlinks_by_inner_cmp);
109RB_GENERATE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
110    hyperlinks_by_inner_cmp);
111
112/* Remove a hyperlink. */
113static void
114hyperlinks_remove(struct hyperlinks_uri *hlu)
115{
116	struct hyperlinks	*hl = hlu->tree;
117
118	TAILQ_REMOVE(&global_hyperlinks, hlu, list_entry);
119	global_hyperlinks_count--;
120
121	RB_REMOVE(hyperlinks_by_inner_tree, &hl->by_inner, hlu);
122	RB_REMOVE(hyperlinks_by_uri_tree, &hl->by_uri, hlu);
123
124	free(__UNCONST(hlu->internal_id));
125	free(__UNCONST(hlu->external_id));
126	free(__UNCONST(hlu->uri));
127	free(hlu);
128}
129
130/* Store a new hyperlink or return if it already exists. */
131u_int
132hyperlinks_put(struct hyperlinks *hl, const char *uri_in,
133    const char *internal_id_in)
134{
135	struct hyperlinks_uri	 find, *hlu;
136	char			*uri, *internal_id, *external_id;
137
138	/*
139	 * Anonymous URI are stored with an empty internal ID and the tree
140	 * comparator will make sure they never match each other (so each
141	 * anonymous URI is unique).
142	 */
143	if (internal_id_in == NULL)
144		internal_id_in = "";
145
146	utf8_stravis(&uri, uri_in, VIS_OCTAL|VIS_CSTYLE);
147	utf8_stravis(&internal_id, internal_id_in, VIS_OCTAL|VIS_CSTYLE);
148
149	if (*internal_id_in != '\0') {
150		find.uri = uri;
151		find.internal_id = internal_id;
152
153		hlu = RB_FIND(hyperlinks_by_uri_tree, &hl->by_uri, &find);
154		if (hlu != NULL) {
155			free (uri);
156			free (internal_id);
157			return (hlu->inner);
158		}
159	}
160	xasprintf(&external_id, "tmux%llX", hyperlinks_next_external_id++);
161
162	hlu = xcalloc(1, sizeof *hlu);
163	hlu->inner = hl->next_inner++;
164	hlu->internal_id = internal_id;
165	hlu->external_id = external_id;
166	hlu->uri = uri;
167	hlu->tree = hl;
168	RB_INSERT(hyperlinks_by_uri_tree, &hl->by_uri, hlu);
169	RB_INSERT(hyperlinks_by_inner_tree, &hl->by_inner, hlu);
170
171	TAILQ_INSERT_TAIL(&global_hyperlinks, hlu, list_entry);
172	if (++global_hyperlinks_count == MAX_HYPERLINKS)
173		hyperlinks_remove(TAILQ_FIRST(&global_hyperlinks));
174
175	return (hlu->inner);
176}
177
178/* Get hyperlink by inner number. */
179int
180hyperlinks_get(struct hyperlinks *hl, u_int inner, const char **uri_out,
181    const char **internal_id_out, const char **external_id_out)
182{
183	struct hyperlinks_uri	find, *hlu;
184
185	find.inner = inner;
186
187	hlu = RB_FIND(hyperlinks_by_inner_tree, &hl->by_inner, &find);
188	if (hlu == NULL)
189		return (0);
190	if (internal_id_out != NULL)
191		*internal_id_out = hlu->internal_id;
192	if (external_id_out != NULL)
193		*external_id_out = hlu->external_id;
194	*uri_out = hlu->uri;
195	return (1);
196}
197
198/* Initialize hyperlink set. */
199struct hyperlinks *
200hyperlinks_init(void)
201{
202	struct hyperlinks	*hl;
203
204	hl = xcalloc(1, sizeof *hl);
205	hl->next_inner = 1;
206	RB_INIT(&hl->by_uri);
207	RB_INIT(&hl->by_inner);
208	return (hl);
209}
210
211/* Free all hyperlinks but not the set itself. */
212void
213hyperlinks_reset(struct hyperlinks *hl)
214{
215	struct hyperlinks_uri	*hlu, *hlu1;
216
217	RB_FOREACH_SAFE(hlu, hyperlinks_by_inner_tree, &hl->by_inner, hlu1)
218		hyperlinks_remove(hlu);
219}
220
221/* Free hyperlink set. */
222void
223hyperlinks_free(struct hyperlinks *hl)
224{
225	hyperlinks_reset(hl);
226	free(hl);
227}
228