hyperlinks.c

   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 #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 }