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
45 static long long hyperlinks_next_external_id = 1;
46 static u_int global_hyperlinks_count;
47
48 struct 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 };
60 RB_HEAD(hyperlinks_by_uri_tree, hyperlinks_uri);
61 RB_HEAD(hyperlinks_by_inner_tree, hyperlinks_uri);
62
63 TAILQ_HEAD(hyperlinks_list, hyperlinks_uri);
64 static struct hyperlinks_list global_hyperlinks =
65 TAILQ_HEAD_INITIALIZER(global_hyperlinks);
66
67 struct hyperlinks {
68 u_int next_inner;
69 struct hyperlinks_by_inner_tree by_inner;
70 struct hyperlinks_by_uri_tree by_uri;
71 u_int references;
72 };
73
74 static int
hyperlinks_by_uri_cmp(struct hyperlinks_uri * left,struct hyperlinks_uri * right)75 hyperlinks_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 }
97 RB_PROTOTYPE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
98 hyperlinks_by_uri_cmp);
99 RB_GENERATE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry,
100 hyperlinks_by_uri_cmp);
101
102 static int
hyperlinks_by_inner_cmp(struct hyperlinks_uri * left,struct hyperlinks_uri * right)103 hyperlinks_by_inner_cmp(struct hyperlinks_uri *left,
104 struct hyperlinks_uri *right)
105 {
106 return (left->inner - right->inner);
107 }
108 RB_PROTOTYPE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
109 hyperlinks_by_inner_cmp);
110 RB_GENERATE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry,
111 hyperlinks_by_inner_cmp);
112
113 /* Remove a hyperlink. */
114 static void
hyperlinks_remove(struct hyperlinks_uri * hlu)115 hyperlinks_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(__UNCONST(hlu->internal_id));
126 free(__UNCONST(hlu->external_id));
127 free(__UNCONST(hlu->uri));
128 free(hlu);
129 }
130
131 /* Store a new hyperlink or return if it already exists. */
132 u_int
hyperlinks_put(struct hyperlinks * hl,const char * uri_in,const char * internal_id_in)133 hyperlinks_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. */
180 int
hyperlinks_get(struct hyperlinks * hl,u_int inner,const char ** uri_out,const char ** internal_id_out,const char ** external_id_out)181 hyperlinks_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. */
200 struct hyperlinks *
hyperlinks_init(void)201 hyperlinks_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 hl->references = 1;
210 return (hl);
211 }
212
213 /* Copy hyperlink set. */
214 struct hyperlinks *
hyperlinks_copy(struct hyperlinks * hl)215 hyperlinks_copy(struct hyperlinks *hl)
216 {
217 hl->references++;
218 return (hl);
219 }
220
221 /* Free all hyperlinks but not the set itself. */
222 void
hyperlinks_reset(struct hyperlinks * hl)223 hyperlinks_reset(struct hyperlinks *hl)
224 {
225 struct hyperlinks_uri *hlu, *hlu1;
226
227 RB_FOREACH_SAFE(hlu, hyperlinks_by_inner_tree, &hl->by_inner, hlu1)
228 hyperlinks_remove(hlu);
229 }
230
231 /* Free hyperlink set. */
232 void
hyperlinks_free(struct hyperlinks * hl)233 hyperlinks_free(struct hyperlinks *hl)
234 {
235 if (--hl->references == 0) {
236 hyperlinks_reset(hl);
237 free(hl);
238 }
239 }
240