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 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 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 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 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 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 * 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 * 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 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 234 hyperlinks_free(struct hyperlinks *hl) 235 { 236 if (--hl->references == 0) { 237 hyperlinks_reset(hl); 238 free(hl); 239 } 240 } 241