1 /* $OpenBSD: hyperlinks.c,v 1.4 2024/08/27 07:49:07 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
46 static long long hyperlinks_next_external_id = 1;
47 static u_int global_hyperlinks_count;
48
49 struct 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 };
61 RB_HEAD(hyperlinks_by_uri_tree, hyperlinks_uri);
62 RB_HEAD(hyperlinks_by_inner_tree, hyperlinks_uri);
63
64 TAILQ_HEAD(hyperlinks_list, hyperlinks_uri);
65 static struct hyperlinks_list global_hyperlinks =
66 TAILQ_HEAD_INITIALIZER(global_hyperlinks);
67
68 struct hyperlinks {
69 u_int next_inner;
70 struct hyperlinks_by_inner_tree by_inner;
71 struct hyperlinks_by_uri_tree by_uri;
72 u_int references;
73 };
74
75 static int
hyperlinks_by_uri_cmp(struct hyperlinks_uri * left,struct hyperlinks_uri * right)76 hyperlinks_by_uri_cmp(struct hyperlinks_uri *left, struct hyperlinks_uri *right)
77 {
78 int r;
79
80 if (*left->internal_id == '\0' || *right->internal_id == '\0') {
81 /*
82 * If both URIs are anonymous, use the inner for comparison so
83 * that they do not match even if the URI is the same - each
84 * anonymous URI should be unique.
85 */
86 if (*left->internal_id != '\0')
87 return (-1);
88 if (*right->internal_id != '\0')
89 return (1);
90 return (left->inner - right->inner);
91 }
92
93 r = strcmp(left->internal_id, right->internal_id);
94 if (r != 0)
95 return (r);
96 return (strcmp(left->uri, right->uri));
97 }
98 RB_PROTOTYPE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
99 hyperlinks_by_uri_cmp);
100 RB_GENERATE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
101 hyperlinks_by_uri_cmp);
102
103 static int
hyperlinks_by_inner_cmp(struct hyperlinks_uri * left,struct hyperlinks_uri * right)104 hyperlinks_by_inner_cmp(struct hyperlinks_uri *left,
105 struct hyperlinks_uri *right)
106 {
107 return (left->inner - right->inner);
108 }
109 RB_PROTOTYPE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
110 hyperlinks_by_inner_cmp);
111 RB_GENERATE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
112 hyperlinks_by_inner_cmp);
113
114 /* Remove a hyperlink. */
115 static void
hyperlinks_remove(struct hyperlinks_uri * hlu)116 hyperlinks_remove(struct hyperlinks_uri *hlu)
117 {
118 struct hyperlinks *hl = hlu->tree;
119
120 TAILQ_REMOVE(&global_hyperlinks, hlu, list_entry);
121 global_hyperlinks_count--;
122
123 RB_REMOVE(hyperlinks_by_inner_tree, &hl->by_inner, hlu);
124 RB_REMOVE(hyperlinks_by_uri_tree, &hl->by_uri, hlu);
125
126 free((void *)hlu->internal_id);
127 free((void *)hlu->external_id);
128 free((void *)hlu->uri);
129 free(hlu);
130 }
131
132 /* Store a new hyperlink or return if it already exists. */
133 u_int
hyperlinks_put(struct hyperlinks * hl,const char * uri_in,const char * internal_id_in)134 hyperlinks_put(struct hyperlinks *hl, const char *uri_in,
135 const char *internal_id_in)
136 {
137 struct hyperlinks_uri find, *hlu;
138 char *uri, *internal_id, *external_id;
139
140 /*
141 * Anonymous URI are stored with an empty internal ID and the tree
142 * comparator will make sure they never match each other (so each
143 * anonymous URI is unique).
144 */
145 if (internal_id_in == NULL)
146 internal_id_in = "";
147
148 utf8_stravis(&uri, uri_in, VIS_OCTAL|VIS_CSTYLE);
149 utf8_stravis(&internal_id, internal_id_in, VIS_OCTAL|VIS_CSTYLE);
150
151 if (*internal_id_in != '\0') {
152 find.uri = uri;
153 find.internal_id = internal_id;
154
155 hlu = RB_FIND(hyperlinks_by_uri_tree, &hl->by_uri, &find);
156 if (hlu != NULL) {
157 free (uri);
158 free (internal_id);
159 return (hlu->inner);
160 }
161 }
162 xasprintf(&external_id, "tmux%llX", hyperlinks_next_external_id++);
163
164 hlu = xcalloc(1, sizeof *hlu);
165 hlu->inner = hl->next_inner++;
166 hlu->internal_id = internal_id;
167 hlu->external_id = external_id;
168 hlu->uri = uri;
169 hlu->tree = hl;
170 RB_INSERT(hyperlinks_by_uri_tree, &hl->by_uri, hlu);
171 RB_INSERT(hyperlinks_by_inner_tree, &hl->by_inner, hlu);
172
173 TAILQ_INSERT_TAIL(&global_hyperlinks, hlu, list_entry);
174 if (++global_hyperlinks_count == MAX_HYPERLINKS)
175 hyperlinks_remove(TAILQ_FIRST(&global_hyperlinks));
176
177 return (hlu->inner);
178 }
179
180 /* Get hyperlink by inner number. */
181 int
hyperlinks_get(struct hyperlinks * hl,u_int inner,const char ** uri_out,const char ** internal_id_out,const char ** external_id_out)182 hyperlinks_get(struct hyperlinks *hl, u_int inner, const char **uri_out,
183 const char **internal_id_out, const char **external_id_out)
184 {
185 struct hyperlinks_uri find, *hlu;
186
187 find.inner = inner;
188
189 hlu = RB_FIND(hyperlinks_by_inner_tree, &hl->by_inner, &find);
190 if (hlu == NULL)
191 return (0);
192 if (internal_id_out != NULL)
193 *internal_id_out = hlu->internal_id;
194 if (external_id_out != NULL)
195 *external_id_out = hlu->external_id;
196 *uri_out = hlu->uri;
197 return (1);
198 }
199
200 /* Initialize hyperlink set. */
201 struct hyperlinks *
hyperlinks_init(void)202 hyperlinks_init(void)
203 {
204 struct hyperlinks *hl;
205
206 hl = xcalloc(1, sizeof *hl);
207 hl->next_inner = 1;
208 RB_INIT(&hl->by_uri);
209 RB_INIT(&hl->by_inner);
210 hl->references = 1;
211 return (hl);
212 }
213
214 /* Copy hyperlink set. */
215 struct hyperlinks *
hyperlinks_copy(struct hyperlinks * hl)216 hyperlinks_copy(struct hyperlinks *hl)
217 {
218 hl->references++;
219 return (hl);
220 }
221
222 /* Free all hyperlinks but not the set itself. */
223 void
hyperlinks_reset(struct hyperlinks * hl)224 hyperlinks_reset(struct hyperlinks *hl)
225 {
226 struct hyperlinks_uri *hlu, *hlu1;
227
228 RB_FOREACH_SAFE(hlu, hyperlinks_by_inner_tree, &hl->by_inner, hlu1)
229 hyperlinks_remove(hlu);
230 }
231
232 /* Free hyperlink set. */
233 void
hyperlinks_free(struct hyperlinks * hl)234 hyperlinks_free(struct hyperlinks *hl)
235 {
236 if (--hl->references == 0) {
237 hyperlinks_reset(hl);
238 free(hl);
239 }
240 }
241