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 }; 72 73 static int 74 hyperlinks_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 } 96 RB_PROTOTYPE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry, 97 hyperlinks_by_uri_cmp); 98 RB_GENERATE_STATIC(hyperlinks_by_uri_tree, hyperlinks_uri, by_uri_entry, 99 hyperlinks_by_uri_cmp); 100 101 static int 102 hyperlinks_by_inner_cmp(struct hyperlinks_uri *left, 103 struct hyperlinks_uri *right) 104 { 105 return (left->inner - right->inner); 106 } 107 RB_PROTOTYPE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry, 108 hyperlinks_by_inner_cmp); 109 RB_GENERATE_STATIC(hyperlinks_by_inner_tree, hyperlinks_uri, by_inner_entry, 110 hyperlinks_by_inner_cmp); 111 112 /* Remove a hyperlink. */ 113 static void 114 hyperlinks_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. */ 131 u_int 132 hyperlinks_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. */ 179 int 180 hyperlinks_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. */ 199 struct hyperlinks * 200 hyperlinks_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. */ 212 void 213 hyperlinks_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. */ 222 void 223 hyperlinks_free(struct hyperlinks *hl) 224 { 225 hyperlinks_reset(hl); 226 free(hl); 227 } 228