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