doc-text.c

   1 /*
   2  * Copyright Neil Brown ©2015 <neil@brown.name>
   3  * May be distributed under terms of GPLv2 - see file:COPYING
   4  *
   5  * Generic text document.
   6  *
   7  * This allows for a file to be read in, and edited by creating
   8  * a linked list of chunks of text - the original isn't changed.
   9  * This means that pointers outside of the edit region are mostly
  10  * left untouched.
  11  *
  12  * Indefinite undo is kept as a record of changes to the list of chunks.
  13  * New text is added to the end of a list of allocations.
  14  *
  15  * Text.
  16  *
  17  * The text of a document is stored in a collection of allocations
  18  * which are immutable once created.  They are attached to the 'document'
  19  * and freed only when the document is discard.
  20  * The current state of the document is represented by a linked list of
  21  * 'chunks' which each point to part of some allocation.
  22  *
  23  * Each chunk can have 'attributes' which add arbitrary annotations to
  24  * ranges of text.  Unlike the text itself, these are not immutable.  Only
  25  * the 'current' attributes are stored.  It is assumed that following
  26  * 'undo', the appropriate attributes can be re-computed.  i.e. they are
  27  * an optimization.
  28  *
  29  * When text is removed from a document, the 'chunk' is modified to
  30  * reference less text.  If the chunk becomes empty, it is discarded.
  31  * When text is added to a document a new chunk is created which
  32  * points to the next free space in the latest allocation, and text is
  33  * added there.  If the text is being added to the end of a chunk and
  34  * it already points to the end of the latest allocation, then no new
  35  * chunk is allocated.
  36  *
  37  * Text is assumed to be UTF-8 encoded.  This becomes relevant when adding
  38  * a string to the document, and it wont all fit in the current allocation.
  39  * In that case we ensure the first byte that goes in the next allocation
  40  * matches 0xxxxxxx or 11xxxxxx., not 10xxxxxx.
  41  *
  42  * Undo/redo information is stored as a list of edits.  Each edit
  43  * changes either the start of the end of a 'chunk'. When a chunk becomes
  44  * empty it is removed from the chunk list.  The 'prev' pointer is preserved
  45  * so when an undo make it non-empty, it knows where to be added back.
  46  *
  47  * A text always has a least one allocation which is created with the text.
  48  * If the text is empty, there will not be any chunks though, so all text refs
  49  * will point to NULL.  The NULL chunk is at the end of the text.
  50  * The ->txt pointer of chunk never changes.  It is set when the chunk is created
  51  * and then only start and end are changed.
  52  */
  53
  54
  55 #define _GNU_SOURCE /* for asprintf */
  56 #include <unistd.h>
  57 #include <stdlib.h>
  58 #include <string.h>
  59 #include <memory.h>
  60 #include <locale.h>
  61 #include <stdio.h>
  62 #include <fcntl.h>
  63 #include <errno.h>
  64
  65 /* A doc_ref is treated as a pointer to a chunk, and an offset
  66  * from the start of 'txt'.  So 'o' must be between c->start and
  67  * c->end inclusive.
  68  */
  69 #define PRIVATE_DOC_REF
  70
  71 struct doc_ref {
  72         struct text_chunk *c;
  73         int o;
  74 };
  75
  76 #include "core.h"
  77 #include "misc.h"
  78
  79 /* text is allocated is large blocks - possibly a whole
  80  * file or some other large unit being added to a document.
  81  * For small additions (normal typing) the default allocation
  82  * size of 4K.
  83  * When more is allocated than needed, extra can be added on to
  84  * the end - 'free' is the next index with free space.
  85  */
  86 struct text_alloc {
  87         struct text_alloc *prev;
  88         int size;
  89         int free;
  90         char text[];
  91 };
  92
  93 #define DEFAULT_SIZE (4096 - sizeof(struct text_alloc))
  94
  95 /* The text document is a list of text_chunk.
  96  * The 'txt' pointer is the text[] of a text_alloc.
  97  * 'start' and 'end' narrow that.
  98  */
  99 struct text_chunk {
 100         char                    *txt;
 101         int                     start;
 102         int                     end;
 103         struct list_head        lst;
 104         struct attrset          *attrs;
 105 };
 106
 107 /* An 'edit' consists of one or more text_edit structs linked together.
 108  * The 'first' text_edit in a group has 'first' set.  So when popping
 109  * off the 'undo' list, we pop until we find the 'first' one.  When
 110  * popping of the 'redo' list, we pop a first, then any following
 111  * non-first entries.
 112  * Each entry identifies a chunk. If 'at_start' is set, the 'len' is
 113  * added to the 'start' pointer (subtracted for undo).  Otherwise
 114  * the len added to the end.  If the resulting length is zero, the
 115  * chunk is removed from the list.
 116  */
 117 struct text_edit {
 118         struct text_chunk       *target;
 119         struct text_edit        *next;
 120         bool                    first:1;
 121         bool                    at_start:1;
 122         int                     len:30; // bytes add, -ve for removed.
 123 };
 124
 125 /* A text document is a document with allocations, a list
 126  * of chunks, and some undo info.
 127  */
 128 struct text {
 129         struct doc              doc;
 130
 131         struct text_alloc       *alloc;
 132         struct list_head        text;
 133         struct text_edit        *undo, *redo;
 134
 135         struct stat             stat;
 136         char                    *fname;
 137 };
 138
 139 static int text_advance_towards(struct text *t, struct doc_ref *ref, struct doc_ref *target);
 140 static int text_retreat_towards(struct text *t, struct doc_ref *ref, struct doc_ref *target);
 141 static int text_ref_same(struct text *t, struct doc_ref *r1, struct doc_ref *r2);
 142 static int text_locate(struct text *t, struct doc_ref *r, struct doc_ref *dest);
 143 static void text_check_consistent(struct text *t);
 144
 145 static struct map *text_map;
 146 /*
 147  * A text will mostly hold utf-8 so we try to align chunk breaks with
 148  * Unicode points.  This particularly affects adding new strings to
 149  * allocations.
 150  * There is no guarantee that a byte string is UTF-8 though, so
 151  * We only adjust the length if we can find a start-of-code-point in
 152  * the last 4 bytes. (longest UTF-8 encoding of 21bit unicode is 4 bytes).
 153  * A start of codepoint starts with 0b0 or 0b11, not 0b10.
 154  */
 155 static int text_round_len(char *text, int len)
 156 {
 157         /* The string at 'text' is *longer* than 'len', or
 158          * at least text[len] is defined - it can be nul.  If
 159          * [len] isn't the start of a new codepoint, and there
 160          * is a start marker in the previous 4 bytes,
 161          * move back to there.
 162          */
 163         int i = 0;
 164         while (i <= len && i <=4)
 165                 if ((text[len-i] & 0xC0) == 0x80)
 166                         /* next byte is inside a UTF-8 code point, so
 167                          * this isn't a good spot to end. Try further
 168                          * back */
 169                         i += 1;
 170                 else
 171                         return len-i;
 172         return len;
 173 }
 174
 175 static struct text_alloc *
 176 text_new_alloc(struct text *t, int size)
 177 {
 178         struct text_alloc *new;
 179         if (size == 0)
 180                 size = DEFAULT_SIZE;
 181         new = malloc(size + sizeof(struct text_alloc));
 182         if (!new)
 183                 return NULL;
 184         new->prev = t->alloc;
 185         t->alloc = new;
 186         new->size = size;
 187         new->free = 0;
 188         return new;
 189 }
 190
 191 DEF_CMD(text_load_file)
 192 {
 193         struct doc_data *dd;
 194         int fd = ci->extra;
 195         char *name = ci->str;
 196         off_t size = lseek(fd, 0, SEEK_END);
 197         struct text_alloc *a;
 198         struct text_chunk *c;
 199         int len;
 200         struct text *t;
 201
 202         if (ci->home)
 203                 dd = ci->home->data;
 204         else
 205                 return -1;
 206         t = container_of(dd->doc, struct text, doc);
 207
 208         if (size < 0)
 209                 goto err;
 210         lseek(fd, 0, SEEK_SET);
 211         if (size > 0) {
 212                 c = malloc(sizeof(*c));
 213                 a = text_new_alloc(t, size);
 214                 if (!a)
 215                         goto err;
 216                 while (a->free < size &&
 217                        (len = read(fd, a->text + a->free, size - a->free)) > 0)
 218                         a->free += len;
 219
 220                 c->txt = a->text;
 221                 c->attrs = NULL;
 222                 c->start = 0;
 223                 c->end = a->free;
 224                 list_add(&c->lst, &t->text);
 225         }
 226         if (name) {
 227                 char *dname;
 228
 229                 fstat(fd, &t->stat);
 230                 free(t->fname);
 231                 t->fname = strdup(name);
 232                 dname = strrchr(name, '/');
 233                 if (dname)
 234                         dname += 1;
 235                 else
 236                         dname = name;
 237                 doc_set_name(dd->doc, dname);
 238         }
 239         return 1;
 240 err:
 241         free(c);
 242         return 0;
 243 }
 244
 245 static int do_text_write_file(struct text *t, char *fname)
 246 {
 247         /* Don't worry about links for now
 248          * Create a temp file with #basename#~, write to that,
 249          * fsync and then rename
 250          */
 251         char *tempname = malloc(strlen(fname) + 3 + 10);
 252         char *base, *tbase;
 253         int cnt = 0;
 254         int fd = -1;
 255         struct text_chunk *c;
 256
 257         strcpy(tempname, fname);
 258         base = strrchr(fname, '/');
 259         if (base)
 260                 base += 1;
 261         else
 262                 base = fname;
 263         tbase = tempname + (base - fname);
 264         while (cnt < 20 && fd == -1) {
 265                 if (cnt)
 266                         sprintf(tbase, "#%s#~%d", base, cnt);
 267                 else
 268                         sprintf(tbase, "#%s#~", base);
 269                 fd = open(tempname, O_WRONLY|O_CREAT|O_EXCL, 0666);
 270                 if (fd < 0 && errno != EEXIST)
 271                         break;
 272                 cnt += 1;
 273         }
 274         if (fd < 0)
 275                 return -1;
 276
 277         list_for_each_entry(c, &t->text, lst) {
 278                 char *s = c->txt + c->start;
 279                 int ln = c->end - c->start;
 280                 if (write(fd, s, ln) != ln)
 281                         goto error;
 282         }
 283         if (fsync(fd) != 0)
 284                 goto error;
 285         if (rename(tempname, fname) < 0)
 286                 goto error;
 287         close(fd);
 288         free(tempname);
 289         return 0;
 290 error:
 291         close(fd);
 292         unlink(tempname);
 293         free(tempname);
 294         return -1;
 295
 296 }
 297
 298 DEF_CMD(text_save_file)
 299 {
 300         struct doc_data *dd = ci->home->data;
 301         struct text *t = container_of(dd->doc, struct text, doc);
 302         int ret;
 303         char *msg;
 304
 305         if (!t->fname) {
 306                 asprintf(&msg, "** No file name known for %s ***", dd->doc->name);
 307                 ret = -1;
 308         } else {
 309                 ret = do_text_write_file(t, t->fname);
 310                 if (ret == 0)
 311                         asprintf(&msg, "Successfully wrote %s", t->fname);
 312                 else
 313                         asprintf(&msg, "*** Faild to write %s ***", t->fname);
 314         }
 315         call5("Message", ci->home, 0, NULL, msg, 0);
 316         free(msg);
 317         if (ret == 0)
 318                 return 1;
 319         return -1;
 320 }
 321
 322 DEF_CMD(text_same_file)
 323 {
 324         struct doc_data *dd = ci->home->data;
 325         struct stat *stb = ci->misc;
 326         struct text *t = container_of(dd->doc, struct text, doc);
 327
 328         if (t->fname == NULL)
 329                 return 0;
 330         if (t->stat.st_ino == stb->st_ino &&
 331             t->stat.st_dev == stb->st_dev)
 332                 return 1;
 333         return 0;
 334 }
 335
 336 static void text_add_edit(struct text *t, struct text_chunk *target,
 337                           bool *first, int at_start, int len)
 338 {
 339         struct text_edit *e;
 340
 341         if (len == 0)
 342                 return;
 343         e = malloc(sizeof(*e));
 344         e->target = target;
 345         e->first = *first;
 346         e->at_start = at_start;
 347         e->len = len;
 348         *first = 0;
 349         e->next = t->undo;
 350         t->undo = e;
 351 }
 352
 353 static void text_add_str(struct text *t, struct doc_ref *pos, char *str,
 354                          struct doc_ref *start, bool *first_edit)
 355 {
 356         /* Text is added to the end of the referenced chunk, or
 357          * in new chunks which are added afterwards.  This allows
 358          * the caller to reliably updated any pointers to accommodate
 359          * changes.
 360          * The added text has no attributes.
 361          *
 362          * 'pos' is moved to point to the end of the inserted text.
 363          * 'start' is set to point to the start which may be the
 364          * original 'pos', or may not if a chunk was inserted.
 365          */
 366         /* easy/common case first: pos is at the end of a chunk,
 367          * which is the last chunk in the current allocation.
 368          */
 369         struct text_alloc *a = t->alloc;
 370         int len = strlen(str);
 371         int len2;
 372
 373         if (start)
 374                 *start = *pos;
 375
 376         len2 = len;
 377         if (pos->c && pos->o == pos->c->end &&
 378             pos->c->txt + pos->o == a->text + a->free &&
 379             (a->size - a->free >= len ||
 380              (len2 = text_round_len(str, a->size - a->free)) > 0)) {
 381                 /* Some of this ('len') can be added to the current chunk */
 382                 len = len2;
 383                 memcpy(a->text+a->free, str, len);
 384                 a->free += len;
 385                 pos->c->end += len;
 386                 pos->o += len;
 387                 str += len;
 388                 text_add_edit(t, pos->c, first_edit, 0, len);
 389                 len = strlen(str);
 390         }
 391         if (!len)
 392                 return;
 393         /* Need a new chunk.  Might need to split the current chunk first.
 394          * Old chunk must be first to simplify updating of pointers */
 395         if (pos->c == NULL || pos->o < pos->c->end) {
 396                 struct text_chunk *c = malloc(sizeof(*c));
 397                 if (pos->c == NULL || pos->o == pos->c->start) {
 398                         /* At the start of a chunk, so create a new one here */
 399                         c->txt = NULL;
 400                         c->start = c->end = 0;
 401                         c->attrs = NULL;
 402                         if (pos->c)
 403                                 list_add_tail(&c->lst, &pos->c->lst);
 404                         else
 405                                 list_add_tail(&c->lst, &t->text);
 406
 407                         if (start && start->c == pos->c && start->o == pos->o) {
 408                                 start->c = c;
 409                                 start->o = c->start;
 410                         }
 411                         pos->c = c;
 412                         pos->o = c->start;
 413                 } else {
 414                         c->txt = pos->c->txt;
 415                         c->start = pos->o;
 416                         c->end = pos->c->end;
 417                         c->attrs = attr_copy_tail(pos->c->attrs, c->start);
 418                         attr_trim(&pos->c->attrs, c->start);
 419                         pos->c->end = pos->o;
 420                         list_add(&c->lst, &pos->c->lst);
 421                         text_add_edit(t, c, first_edit, 0, c->end - c->start);
 422                         /* this implicitly truncates pos->c, so don't need to record that. */
 423                 }
 424         }
 425         while ((len = strlen(str)) > 0) {
 426                 /* Make sure we have an empty chunk */
 427                 if (pos->c->end > pos->c->start) {
 428                         struct text_chunk *c = malloc(sizeof(*c));
 429                         c->start = c->end = 0;
 430                         c->attrs = NULL;
 431                         list_add(&c->lst, &pos->c->lst);
 432                         if (start && start->c == pos->c && start->o == pos->o) {
 433                                 start->c = c;
 434                                 start->o = 0;
 435                         }
 436                         pos->c = c;
 437                         pos->o = c->start;
 438                 }
 439                 /* Make sure we have some space in 'a' */
 440                 if (a->size - a->free < len &&
 441                     (len = text_round_len(str, a->size - a->free)) == 0) {
 442                         a = text_new_alloc(t, 0);
 443                         len = strlen(str);
 444                         if (len > a->size)
 445                                 len = text_round_len(str, a->size);
 446                 }
 447                 pos->c->txt = a->text + a->free;
 448                 pos->c->end = len;
 449                 pos->o = len;
 450                 memcpy(a->text + a->free, str, len);
 451                 text_add_edit(t, pos->c, first_edit, 0, len);
 452                 a->free += len;
 453                 str += len;
 454         }
 455 }
 456
 457 /* Text insertion, deletion, and undo can modify chunks which various
 458  * marks point to - so those marks will need to be updated.
 459  * Modification include splitting a chunk, inserting chunks,
 460  * or deleting chunks and recombining chunks (for undo).
 461  * Also reducing or increasing the range of a chunk.
 462  * When a chunk is split, the original becomes the first part.
 463  * So any mark pointing past the end of that original must be moved
 464  * to the new chunk.
 465  * When a chunk is deleted, any mark pointing to a deleted chunk
 466  * must be redirected to the (new) point of deletion.
 467  * When a chunk is inserted, marks before the insertion mark must remain
 468  * before the inserted chunk, marks after must remain after the insertion
 469  * point.
 470  * When two chunks are recombined it will appear that the second chunk
 471  * was deleted.  In this case though, references to the second chunk need
 472  * to be repositioned in the first.
 473  * When range is reduced, offset must be moved back into range.
 474  * When range is increased, and this mark is after change, offset in this mark
 475  * need to line up with changed point.
 476  *
 477  * So text_update_prior_after_change() is called on marks before the
 478  * mark-of-change in reverse order until the function returns zero.
 479  * If it finds a mark pointing to a deleted chunk, that mark changes to
 480  * point the same place as the mark-of-change.
 481  * If it finds a mark at, or immediately after, the mark-of-change,
 482  * that mark is moved to point to the start of insert.
 483  *
 484  * Then text_update_following_after_change() is called on marks after
 485  * the mark-of-change in order until that function returns zero.
 486  * If a mark points outside the range of a chunk, the other half of the
 487  * chunk is found (by walking forward) and the pointer is updated.
 488  * If a deleted chunk is found, that mark is redirected to the mark-of-change.
 489  * If a location at the start is found, it is move to the end.
 490  */
 491
 492 static int text_update_prior_after_change(struct text *t, struct doc_ref *pos,
 493                                           struct doc_ref *spos, struct doc_ref *epos)
 494 {
 495
 496         if (pos->c == NULL) {
 497                 /* Was at the end, now must be at the start of the change */
 498                 *pos = *spos;
 499                 return 1;
 500         }
 501
 502         if (pos->c->start >= pos->c->end) {
 503                 /* This chunk was deleted */
 504                 *pos = *epos;
 505                 return 1;
 506         }
 507         if (text_ref_same(t, pos, epos)) {
 508                 *pos = *spos;
 509                 return 1;
 510         }
 511         if (pos->o < pos->c->start) {
 512                 /* Text deleted from under me */
 513                 pos->o = pos->c->start;
 514                 return 1;
 515         }
 516         if (pos->o > pos->c->end) {
 517                 /* Text deleted under me */
 518                 pos->o = pos->c->end;
 519                 return 1;
 520         }
 521         /* no insert or delete here, so all done */
 522         return 0;
 523 }
 524
 525 static int text_update_following_after_change(struct text *t, struct doc_ref *pos,
 526                                               struct doc_ref *spos, struct doc_ref *epos)
 527 {
 528         /* A change has happened between spos and epos. pos should be at or after
 529          * epos.
 530          */
 531         struct text_chunk *c;
 532
 533         if (pos->c == NULL)
 534                 return 1;
 535
 536         if (pos->c->start >= pos->c->end) {
 537                 /* This chunk was deleted */
 538                 if (epos->c &&
 539                     pos->c->txt == epos->c->txt &&
 540                     pos->o >= epos->c->start &&
 541                     pos->o <= epos->c->end)
 542                         /* chunks were rejoined */
 543                         pos->c = epos->c;
 544                 else
 545                         *pos = *epos;
 546                 return 1;
 547         }
 548         if (pos->c == epos->c &&
 549             pos->o < epos->o) {
 550                 /* Text inserted, need to push forward. */
 551                 pos->o = epos->o;
 552                 return 1;
 553         }
 554         if (pos->o < pos->c->start) {
 555                 /* must have been deleted... */
 556                 pos->o = pos->c->start;
 557                 return 1;
 558         }
 559         if (pos->o > pos->c->end) {
 560                 /* This was split, or text was deleted off the end */
 561
 562                 c = epos->c;
 563                 if (c)
 564                         list_for_each_entry_from(c, &t->text, lst) {
 565                                 if (c->txt == pos->c->txt &&
 566                                     c->start <= pos->o &&
 567                                     c->end >= pos->o) {
 568                                         pos->c = c;
 569                                         break;
 570                                 }
 571                         }
 572                 if (pos->o > pos->c->end)
 573                         /* no split found, so just a delete */
 574                         pos->o = pos->c->end;
 575                 return 1;
 576         }
 577         if (text_ref_same(t, pos, spos)) {
 578                 *pos = *epos;
 579                 return 1;
 580         }
 581         /* HACK? */
 582         if (text_ref_same(t, pos, epos))
 583                 /* KEep going*/
 584                 return 1;
 585         /* This is beyond the change point and no deletion or split
 586          * happened here, so all done.
 587          */
 588         return 0;
 589 }
 590
 591 static void text_del(struct text *t, struct doc_ref *pos, int len, bool *first_edit)
 592 {
 593         while (len) {
 594                 struct text_chunk *c = pos->c;
 595                 if (c == NULL)
 596                         /* nothing more to delete */
 597                         break;
 598                 if (pos->o == pos->c->start &&
 599                     len >= pos->c->end - pos->c->start) {
 600                         /* The whole chunk is deleted, simply disconnect it */
 601                         if (c->lst.next != &t->text) {
 602                                 pos->c = list_next_entry(c, lst);
 603                                 pos->o = pos->c->start;
 604                         } else if (c->lst.prev != &t->text) {
 605                                 pos->c = list_prev_entry(c, lst);
 606                                 pos->o = pos->c->end;
 607                         } else {
 608                                 /* Deleted final chunk */
 609                                 pos->c = NULL;
 610                                 pos->o = 0;
 611                         }
 612                         __list_del(c->lst.prev, c->lst.next); /* no poison, retain place in list */
 613                         attr_free(&c->attrs);
 614                         text_add_edit(t, c, first_edit, 0, c->start - c->end);
 615                         len -= c->end - c->start;
 616                         c->end = c->start;
 617                 } else if (pos->o == pos->c->start) {
 618                         /* If the start of the chunk is deleted, just update */
 619                         struct attrset *s;
 620                         c->start += len;
 621                         pos->o = c->start;
 622                         s = attr_copy_tail(c->attrs, c->start);
 623                         attr_free(&c->attrs);
 624                         c->attrs = s;
 625                         text_add_edit(t, c, first_edit, 1, len);
 626                         len = 0;
 627                 } else if (c->end - pos->o <= len) {
 628                         /* If the end of the chunk is deleted, just update
 629                          * and move forward */
 630                         int diff = c->end - pos->o;
 631                         len -= diff;
 632                         c->end = pos->o;
 633                         attr_trim(&c->attrs, c->end);
 634                         text_add_edit(t, c, first_edit, 0, -diff);
 635                         if (len && c->lst.next != &t->text) {
 636                                 pos->c = list_next_entry(c, lst);
 637                                 pos->o = pos->c->start;
 638                         } else
 639                                 len = 0;
 640                 } else {
 641                         /* must be deleting out of the middle of the chunk.
 642                          * need to create new chunk for the 'after' bit.
 643                          */
 644                         struct text_chunk *c2 = malloc(sizeof(*c2));
 645                         c2->txt = c->txt;
 646                         c2->start = pos->o + len;
 647                         c2->end = c->end;
 648                         c->end = pos->o;
 649                         c2->attrs = attr_copy_tail(c->attrs, c2->start);
 650                         attr_trim(&c->attrs, c->end);
 651                         list_add(&c2->lst, &c->lst);
 652                         text_add_edit(t, c2, first_edit, 0, c2->end - c2->start);
 653                         text_add_edit(t, c, first_edit, 0, -len);
 654                         len = 0;
 655                 }
 656         }
 657 }
 658
 659 /* text_undo and text_redo return:
 660  * 0 - there are no more changes to do
 661  * 1 - A change has been done, there are no more parts to it.
 662  * 2 - A change has been partially undone - call again to undo more.
 663  *
 664  * The 'start' and 'end' reported identify the range changed.  For a reversed insertion
 665  * they will be the same.  If the undo results in the buffer being empty,
 666  * both start and end will point to a NULL chunk.
 667  * When undoing a split, both will be at the point of the split.
 668  */
 669 static int text_undo(struct text *t, struct doc_ref *start, struct doc_ref *end)
 670 {
 671         struct text_edit *e = t->undo;
 672
 673         if (!e)
 674                 return 0;
 675
 676         if (e->target->end == e->target->start) {
 677                 /* need to re-link */
 678                 struct list_head *l = e->target->lst.prev;
 679                 list_add(&e->target->lst, l);
 680         }
 681         start->c = end->c = e->target;
 682         start->o = e->target->end; // incase was deletion at end
 683         end->o = e->target->start; // incase was deletion at start
 684         if (e->at_start) {
 685                 e->target->start -= e->len;
 686                 if (e->len > 0)
 687                         /* was deletion, this is insertion */
 688                         start->o = e->target->start;
 689                 else
 690                         /* was insertion - not really possible */
 691                         start->o = end->o = e->target->start;
 692         } else {
 693                 e->target->end -= e->len;
 694                 if (e->len > 0)
 695                         /* Was insertion, now deleting */
 696                         start->o = end->o = e->target->end;
 697                 else
 698                         /* Was deletion, now inserting */
 699                         end->o = e->target->end;
 700         }
 701         t->undo = e->next;
 702         e->next = t->redo;
 703         t->redo = e;
 704         if (e->target->start == e->target->end) {
 705                 /* The undo deletes this chunk, so it must have been inserted,
 706                  * either as new text or for a chunk-split.
 707                  * If new text, leave start/end pointing just past the chunk.
 708                  * if split, leave them at the point of splitting.
 709                  */
 710                 if (e->target->lst.next == &t->text) {
 711                         end->c = NULL;
 712                         end->o = 0;
 713                 } else {
 714                         end->c = list_next_entry(e->target, lst);
 715                         end->o = end->c->start;
 716                 }
 717                 *start = *end;
 718
 719                 __list_del(e->target->lst.prev, e->target->lst.next);
 720                 /* If this was created for a split, we need to extend the other half */
 721                 if (e->target->lst.prev != &t->text) {
 722                         struct text_chunk *c = list_prev_entry(e->target, lst);
 723                         start->c = end->c = c;
 724                         start->o = end->o = c->end;
 725                         if (c->txt == e->target->txt &&
 726                             c->end == e->target->start &&
 727                             !e->at_start)
 728                                 c->end += e->len;
 729                 }
 730         }
 731         if (e->first)
 732                 return 1;
 733         else
 734                 return 2;
 735 }
 736
 737 static int text_redo(struct text *t, struct doc_ref *start, struct doc_ref *end)
 738 {
 739         struct text_edit *e = t->redo;
 740         int is_split = 0;
 741
 742         if (!e)
 743                 return 0;
 744
 745         if (e->target->end == e->target->start) {
 746                 /* need to re-link */
 747                 struct list_head *l = e->target->lst.prev;
 748                 list_add(&e->target->lst, l);
 749                 /* If this is a split, need to truncate prior */
 750                 if (e->target->lst.prev != &t->text) {
 751                         struct text_chunk *c = list_prev_entry(e->target, lst);
 752                         if (c->txt == e->target->txt &&
 753                             c->end > e->target->start) {
 754                                 c->end = e->target->start;
 755                                 is_split = 1;
 756                         }
 757                 }
 758         }
 759         start->c = end->c = e->target;
 760         end->o = e->target->start; // incase is insertion at start
 761         start->o = e->target->end; // incase inserting at end
 762         if (e->at_start) {
 763                 e->target->start += e->len;
 764                 if (e->len > 0)
 765                         /* deletion at start */
 766                         start->o = end->o = e->target->start;
 767                 else
 768                         /* Insertion at start, not currently possible */
 769                         start->o = e->target->start;
 770         } else {
 771                 e->target->end += e->len;
 772                 if (e->len > 0)
 773                         /* Insertion at end */
 774                         end->o = e->target->end;
 775                 else if (is_split)
 776                         start->o = end->o = e->target->start;
 777                 else
 778                         /* Deletion at end */
 779                         start->o = end->o = e->target->end;
 780         }
 781         t->redo = e->next;
 782         e->next = t->undo;
 783         t->undo = e;
 784         if (e->target->start == e->target->end) {
 785                 /* This chunk is deleted, so leave start/end pointing beyond it */
 786                 if (e->target->lst.next == &t->text) {
 787                         end->c = NULL;
 788                         end->o = 0;
 789                 } else {
 790                         end->c = list_next_entry(e->target, lst);
 791                         end->o = end->c->start;
 792                 }
 793                 *start = *end;
 794
 795                 __list_del(e->target->lst.prev, e->target->lst.next);
 796         }
 797         if (t->redo && t->redo->first)
 798                 return 1;
 799         else
 800                 return 2;
 801 }
 802
 803 DEF_CMD(text_reundo)
 804 {
 805         struct doc_data *dd = ci->home->data;
 806         struct mark *m = dd->point;
 807         bool redo = ci->numeric != 0;
 808         struct doc_ref start, end;
 809         int did_do = 2;
 810         bool first = 1;
 811         struct text *t = container_of(dd->doc, struct text, doc);
 812
 813         while (did_do != 1) {
 814                 struct mark *m2;
 815                 struct mark *early = NULL;
 816                 int where;
 817                 int i;
 818
 819                 if (redo)
 820                         did_do = text_redo(t, &start, &end);
 821                 else
 822                         did_do = text_undo(t, &start, &end);
 823                 if (did_do == 0)
 824                         break;
 825
 826                 if (first) {
 827                         /* Not nearby, look from the start */
 828                         mark_reset(&t->doc, m);
 829                         where = 1;
 830                         first = 0;
 831                 } else
 832                         where = text_locate(t, &m->ref, &end);
 833                 if (!where)
 834                         break;
 835
 836                 if (where == 1) {
 837                         do {
 838                                 i = text_advance_towards(t, &m->ref, &end);
 839                                 if (i == 0)
 840                                         break;
 841                                 while ((m2 = doc_next_mark_all(m)) != NULL &&
 842                                        m2->ref.c == m->ref.c &&
 843                                        m2->ref.o <= m->ref.o)
 844                                         mark_forward_over(m, m2);
 845                         } while (i == 2);
 846                 } else {
 847                         do {
 848                                 i = text_retreat_towards(t, &m->ref, &end);
 849                                 if (i == 0)
 850                                         break;
 851                                 while ((m2 = doc_prev_mark_all(m)) != NULL &&
 852                                        m2->ref.c == m->ref.c &&
 853                                        m2->ref.o >= m->ref.o)
 854                                         mark_backward_over(m, m2);
 855                         } while (i == 2);
 856                 }
 857
 858                 if (!text_ref_same(t, &m->ref, &end))
 859                         /* eek! */
 860                         break;
 861                 /* point is now at location of undo */
 862
 863                 m2 = m;
 864                 hlist_for_each_entry_continue_reverse(m2, all)
 865                         if (text_update_prior_after_change(t, &m2->ref,
 866                                                            &start, &end) == 0)
 867                                 break;
 868                 m2 = m;
 869                 hlist_for_each_entry_continue(m2, all)
 870                         if (text_update_following_after_change(t, &m2->ref,
 871                                                                &start, &end) == 0)
 872                                 break;
 873
 874                 early = doc_prev_mark_all(m);
 875                 if (early && !text_ref_same(t, &early->ref, &start))
 876                         early = NULL;
 877
 878                 doc_notify_change(&t->doc, dd->point, early);
 879
 880                 text_check_consistent(t);
 881         }
 882         text_check_consistent(t);
 883         return did_do;
 884 }
 885
 886 #ifdef DEBUG
 887
 888 static int common_prefix(char *a, char *b, int l)
 889 {
 890         int i = 0;
 891         while (i < l &&
 892                a[i] == b[i])
 893                 i++;
 894         return i;
 895 }
 896
 897 /* Compare a string with the text.
 898  * Update the ref passed all matching chars.
 899  * Return length that was matched.
 900  */
 901 static int text_str_cmp(struct text *t, struct doc_ref *r, char *s)
 902 {
 903         struct text_chunk *c = r->c;
 904         int o = r->o;
 905         int matched = 0;
 906
 907         if (c == NULL)
 908                 return 0;
 909
 910         list_for_each_entry_from(c, &t->text, lst) {
 911                 int l = strlen(s);
 912                 if (o == 0)
 913                         o = c->start;
 914                 if (c->end - o < l)
 915                         l = c->end - o;
 916                 l = common_prefix(c->txt+o, s, l);
 917                 matched += l;
 918                 o += l;
 919                 if (s[l] == 0)
 920                         break;
 921                 if (l == c->end - o)
 922                         break;
 923                 s += l;
 924                 o = 0;
 925         }
 926         r->c = c;
 927         r->o = o;
 928         return matched;
 929 }
 930 #endif
 931
 932 static wint_t text_next(struct text *t, struct doc_ref *r)
 933 {
 934         wchar_t ret;
 935         int err;
 936         mbstate_t ps = {0};
 937
 938         if (r->c == NULL)
 939                 return WEOF;
 940
 941         if (r->o >= r->c->end) {
 942                 if (r->c->lst.next == &t->text)
 943                         return WEOF;
 944                 r->c = list_next_entry(r->c, lst);
 945                 r->o = r->c->start;
 946         }
 947
 948         err = mbrtowc(&ret, r->c->txt + r->o, r->c->end - r->o, &ps);
 949         if (err > 0) {
 950                 ASSERT(text_round_len(r->c->txt, r->o+err-1) == r->o);
 951                 r->o += err;
 952                 return ret;
 953         }
 954         ret = (unsigned char)r->c->txt[r->o++];
 955         return ret;
 956 }
 957
 958 static wint_t text_prev(struct text *t, struct doc_ref *r)
 959 {
 960         wchar_t ret;
 961         int err;
 962         mbstate_t ps = {0};
 963
 964         if (r->c == NULL) {
 965                 if (list_empty(&t->text))
 966                         return WEOF;
 967                 r->c = list_entry(t->text.prev, struct text_chunk, lst);
 968                 r->o = r->c->end;
 969         }
 970
 971         if (r->o <= r->c->start) {
 972                 if (r->c->lst.prev == &t->text)
 973                         return WEOF;
 974                 r->c = list_prev_entry(r->c, lst);
 975                 r->o = r->c->end;
 976         }
 977         r->o = r->c->start +
 978                 text_round_len(r->c->txt+r->c->start, r->o - r->c->start - 1);
 979         err = mbrtowc(&ret, r->c->txt + r->o, r->c->end - r->o, &ps);
 980         if (err > 0)
 981                 return ret;
 982
 983         ret = (unsigned char)r->c->txt[r->o];
 984         return ret;
 985 }
 986
 987 DEF_CMD(text_step)
 988 {
 989         struct doc_data *dd = ci->home->data;
 990         struct mark *m = ci->mark;
 991         bool forward = ci->numeric;
 992         bool move = ci->extra;
 993
 994         struct text *t = container_of(dd->doc, struct text, doc);
 995         struct doc_ref r;
 996         wint_t ret;
 997
 998         r = m->ref;
 999         if (forward)
1000                 ret = text_next(t, &r);
1001         else
1002                 ret = text_prev(t, &r);
1003         if (ret != WEOF && move)
1004                 m->ref = *(struct doc_ref*)&r;
1005         /* return value must be +ve, so use high bits to ensure this. */
1006         return (ret & 0xFFFFF) | 0x100000;
1007 }
1008
1009 static int text_ref_same(struct text *t, struct doc_ref *r1, struct doc_ref *r2)
1010 {
1011         if (r1->c == r2->c) {
1012                 if (r1->o == r2->o)
1013                         return 1;
1014                 if (r1->c == NULL)
1015                         return 0;
1016                 /* if references are in the middle of a UTF-8 encoded
1017                  * char, accept as same if it is same char
1018                  */
1019                 if (r1->o == r1->c->end ||
1020                     r2->o == r2->c->end)
1021                         return 0;
1022                 return text_round_len(r1->c->txt, r1->o) ==
1023                         text_round_len(r1->c->txt, r2->o);
1024         }
1025         if (r1->c == NULL) {
1026                 if (list_empty(&t->text))
1027                         return 1;
1028                 return (r2->o == r2->c->end &&
1029                         r2->c->lst.next == &t->text);
1030         }
1031         if (r2->c == NULL) {
1032                 if (list_empty(&t->text))
1033                         return 1;
1034                 return (r1->o == r1->c->end &&
1035                         r1->c->lst.next == &t->text);
1036         }
1037
1038         if (r1->o == r1->c->end &&
1039             r2->o == r2->c->start &&
1040             list_next_entry(r1->c, lst) == r2->c)
1041                 return 1;
1042         if (r1->o == r1->c->start &&
1043             r2->o == r2->c->end &&
1044             list_prev_entry(r1->c, lst) == r2->c)
1045                 return 1;
1046         return 0;
1047 }
1048
1049 DEF_CMD(text_mark_same)
1050 {
1051         struct doc_data *dd = ci->home->data;
1052         struct text *t = container_of(dd->doc, struct text, doc);
1053
1054         return text_ref_same(t, &ci->mark->ref, &ci->mark2->ref) ? 1 : 2;
1055 }
1056
1057 DEF_CMD(text_new)
1058 {
1059         struct text *t = malloc(sizeof(*t));
1060         struct editor *ed = pane2ed(ci->focus);
1061         struct pane *p;
1062
1063         t->alloc = NULL;
1064         INIT_LIST_HEAD(&t->text);
1065         t->undo = t->redo = NULL;
1066         doc_init(&t->doc);
1067         t->doc.map = text_map;
1068         t->fname = NULL;
1069         text_new_alloc(t, 0);
1070         p = doc_attach(ed->root.focus, &t->doc);
1071         if (p)
1072                 return comm_call(ci->comm2, "callback:doc", p, 0, NULL, NULL, 0);
1073         return -1;
1074 }
1075
1076 static int count_bytes(struct text *t, struct mark *from, struct mark *to)
1077 {
1078         struct text_chunk *c, *first, *last;
1079         int l = 0, head, tail;
1080
1081         first = list_first_entry_or_null(&t->text, struct text_chunk, lst);
1082         head = 0;
1083         if (from && from->ref.c) {
1084                 first = from->ref.c;
1085                 head = from->ref.o - first->start;
1086         }
1087         last = NULL;
1088         tail = 0;
1089         if (to && to->ref.c) {
1090                 last = to->ref.c;
1091                 tail = last->end - to->ref.o;
1092         }
1093         c = first;
1094         list_for_each_entry_from(c, &t->text, lst) {
1095                 l += c->end - c->start;
1096                 if (c == first)
1097                         l -= head;
1098                 if (c == last) {
1099                         l -= tail;
1100                         break;
1101                 }
1102         }
1103         return l;
1104 }
1105
1106 DEF_CMD(text_get_str)
1107 {
1108         struct doc_data *dd = ci->home->data;
1109         struct mark *from = NULL, *to = NULL;
1110         struct text *t = container_of(dd->doc, struct text, doc);
1111         struct text_chunk *c, *first, *last;
1112         char *ret;
1113         int l = 0, head, tail;
1114
1115         if (ci->mark && ci->mark2) {
1116                 if (mark_ordered(ci->mark2, ci->mark)) {
1117                         from = ci->mark2;
1118                         to = ci->mark;
1119                 } else {
1120                         from = ci->mark;
1121                         to = ci->mark2;
1122                 }
1123         }
1124
1125         first = list_first_entry_or_null(&t->text, struct text_chunk, lst);
1126         head = 0;
1127         if (from && from->ref.c) {
1128                 first = from->ref.c;
1129                 head = from->ref.o - first->start;
1130         }
1131         last = NULL;
1132         tail = 0;
1133         if (to && to->ref.c) {
1134                 last = to->ref.c;
1135                 tail = last->end - to->ref.o;
1136         }
1137         c = first;
1138         list_for_each_entry_from(c, &t->text, lst) {
1139                 l += c->end - c->start;
1140                 if (c == first)
1141                         l -= head;
1142                 if (c == last) {
1143                         l -= tail;
1144                         break;
1145                 }
1146         }
1147         ret = malloc(l+1);
1148         l = 0;
1149         c = first;
1150         list_for_each_entry_from(c, &t->text, lst) {
1151                 char *s = c->txt + c->start;
1152                 int ln = c->end - c->start;
1153                 if (c == first) {
1154                         s += head;
1155                         ln -= head;
1156                 }
1157                 if (c == last)
1158                         ln -= tail;
1159                 memcpy(ret+l, s, ln);
1160                 l += ln;
1161                 if (c == last)
1162                         break;
1163         }
1164         ret[l] = 0;
1165         comm_call(ci->comm2, "callback:get-str", ci->focus, 0, NULL, ret, 0);
1166         free(ret);
1167         return 1;
1168 }
1169
1170 DEF_CMD(text_set_ref)
1171 {
1172         struct doc_data *dd = ci->home->data;
1173         struct mark *m = ci->mark;
1174         struct text *t = container_of(dd->doc, struct text, doc);
1175
1176         if (list_empty(&t->text) || ci->numeric != 1) {
1177                 m->ref.c = NULL;
1178                 m->ref.o = 0;
1179         } else {
1180                 m->ref.c = list_first_entry(&t->text, struct text_chunk, lst);
1181                 m->ref.o = m->ref.c->start;
1182         }
1183         m->rpos = 0;
1184         return 1;
1185 }
1186
1187 static int text_advance_towards(struct text *t, struct doc_ref *ref, struct doc_ref *target)
1188 {
1189         /* Move 'ref' towards 'target'.
1190          * If at end of chunk, step to next chunk, then
1191          * advance to 'target' or to end of chunk, whichever comes first.
1192          * return:
1193          * 0 - reached end of text
1194          * 1 - found target
1195          * 2 - on a new chunk, keep looking.
1196          */
1197         if (ref->c == target->c) {
1198                 if (ref->o > target->o)
1199                         /* will never find it */
1200                         return 0;
1201                 ref->o = target->o;
1202                 return 1;
1203         }
1204         if (ref->c == NULL) {
1205                 if (target->c->lst.next == &t->text &&
1206                     target->o == target->c->end)
1207                         return 1;
1208                 return 0;
1209         }
1210         if (ref->o >= ref->c->end) {
1211                 if (ref->c->lst.next == &t->text) {
1212                         if (target->c == NULL) {
1213                                 ref->c = NULL;
1214                                 ref->o = 0;
1215                                 return 1;
1216                         }
1217                         return 0;
1218                 }
1219                 ref->c = list_next_entry(ref->c, lst);
1220                 ref->o = ref->c->start;
1221         }
1222         if (ref->c == target->c) {
1223                 if (ref->o > target->o)
1224                         /* will never find it */
1225                         return 0;
1226                 ref->o = target->o;
1227                 return 1;
1228         }
1229         ref->o = ref->c->end;
1230         return 2;
1231 }
1232
1233 static int text_retreat_towards(struct text *t, struct doc_ref *ref, struct doc_ref *target)
1234 {
1235         /* Move 'ref' towards 'target'.
1236          * If at end of chunk, step to next chunk, then
1237          * advance to 'target' or to end of chunk, whichever comes first.
1238          * return:
1239          * 0 - reached start of text
1240          * 1 - found target
1241          * 2 - on a new chunk, keep looking.
1242          */
1243         if (ref->c == NULL) {
1244                 if (list_empty(&t->text))
1245                         return 0;
1246                 ref->c = list_entry(t->text.prev, struct text_chunk, lst);
1247                 ref->o = ref->c->end;
1248         }
1249         if (ref->o <= ref->c->start) {
1250                 if (ref->c->lst.prev == &t->text)
1251                         return 0;
1252                 ref->c = list_prev_entry(ref->c, lst);
1253                 ref->o = ref->c->end;
1254         }
1255         if (ref->c == target->c) {
1256                 ref->o = target->o;
1257                 return 1;
1258         }
1259         ref->o = ref->c->start;
1260         return 2;
1261 }
1262
1263 static int text_locate(struct text *t, struct doc_ref *r, struct doc_ref *dest)
1264 {
1265         /* move back/forward a little from 'r' looking for 'dest'.
1266          * return 0 if not found, -1 if dest found before r.
1267          * return 1 if dest found after or at r.
1268          */
1269         struct text_chunk *next, *prev;
1270
1271         if (r->c == NULL) {
1272                 if (dest->c == NULL)
1273                         return 1;
1274                 else
1275                         return -1;
1276         }
1277         if (dest->c == NULL)
1278                 return 1;
1279         if (r->c == dest->c) {
1280                 if (dest->o < r->o)
1281                         return -1;
1282                 else
1283                         return 1;
1284         }
1285         next = (r->c->lst.next == &t->text) ? NULL : list_next_entry(r->c, lst);
1286         prev = (r->c->lst.prev == &t->text) ? NULL : list_prev_entry(r->c, lst);
1287         if (next == dest->c)
1288                 return 1;
1289         if (prev == dest->c)
1290                 return -1;
1291
1292         next = (next == NULL || next->lst.next == &t->text) ? NULL : list_next_entry(next, lst);
1293         prev = (prev == NULL || prev->lst.prev == &t->text) ? NULL : list_prev_entry(prev, lst);
1294         if (next == dest->c)
1295                 return 1;
1296         if (prev == dest->c)
1297                 return -1;
1298         return 0;
1299 }
1300
1301 static void check_allocated(struct text *t, char *buf, int len)
1302 {
1303         struct text_alloc *ta = t->alloc;
1304         for (ta = t->alloc; ta; ta = ta->prev) {
1305                 if (buf >= ta->text && buf+len <= ta->text + ta->free)
1306                         return;
1307         }
1308         abort();
1309 }
1310
1311 static void text_ref_consistent(struct text *t, struct doc_ref *r)
1312 {
1313         struct text_chunk *c;
1314
1315         if (r->c == NULL) {
1316                 if (r->o)
1317                         abort();
1318                 return;
1319         }
1320         if (r->o > r->c->end)
1321                 abort();
1322         if (r->o < r->c->start)
1323                 abort();
1324         list_for_each_entry(c, &t->text, lst)
1325                 if (r->c == c)
1326                         return;
1327         abort();
1328 }
1329
1330 static void text_check_consistent(struct text *t)
1331 {
1332         /* make sure text is consistent, and abort if not.
1333          * - each chunk points to allocated space
1334          * - no two chunks overlap
1335          * - no chunks are empty
1336          * - every mark points to a valid chunk with valid offset
1337          * - all marks are in text order
1338          */
1339         struct text_chunk *c;
1340         struct mark *m, *prev;
1341         struct doc *d = &t->doc;
1342
1343         list_for_each_entry(c, &t->text, lst) {
1344                 check_allocated(t, c->txt, c->end);
1345                 if (c->start >= c->end)
1346                         abort();
1347                 if (c->start < 0)
1348                         abort();
1349         }
1350         list_for_each_entry(c, &t->text, lst) {
1351                 struct text_chunk *c2;
1352                 list_for_each_entry(c2, &t->text, lst) {
1353                         if (c2 == c ||
1354                             c2->txt != c->txt)
1355                                 continue;
1356                         if (c->start >= c2->end)
1357                                 continue;
1358                         if (c2->start >= c->end)
1359                                 continue;
1360                         abort();
1361                 }
1362         }
1363
1364         for (m = doc_first_mark_all(d); m; m = doc_next_mark_all(m))
1365                 text_ref_consistent(t, &m->ref);
1366
1367         prev = NULL;
1368         for (m = doc_first_mark_all(d); m; m = doc_next_mark_all(m)) {
1369                 if (prev) {
1370                         struct doc_ref r = prev->ref;
1371                         int i;
1372
1373                         while ((i = text_advance_towards(t, &r, &m->ref)) != 1) {
1374                                 if (i == 0)
1375                                         abort();
1376                         }
1377                 }
1378                 prev = m;
1379         }
1380         doc_check_consistent(d);
1381 }
1382
1383 DEF_CMD(text_replace)
1384 {
1385         struct doc_data *dd = ci->home->data;
1386         struct text *t = container_of(dd->doc, struct text, doc);
1387         struct mark *pm = dd->point;
1388         struct mark *end = ci->mark;
1389         char *str = ci->str;
1390         bool first = ci->extra;
1391         struct mark *early = NULL;
1392
1393         /* First delete, then insert */
1394         if (end && !text_ref_same(t, &pm->ref, &end->ref)) {
1395                 struct mark *myend, *m;
1396                 int l;
1397
1398                 if (!mark_ordered(pm, end)) {
1399                         myend = mark_dup(pm, 1);
1400                         mark_to_mark(pm, end);
1401                 } else
1402                         myend = mark_dup(end, 1);
1403                 l = count_bytes(t, pm, myend);
1404                 mark_free(myend);
1405                 text_del(t, &pm->ref, l, &first);
1406
1407                 for (m = doc_prev_mark_all(pm);
1408                      m && text_update_prior_after_change(t, &m->ref, &pm->ref, &pm->ref);
1409                      m = doc_prev_mark_all(m))
1410                         ;
1411                 for (m = doc_next_mark_all(pm);
1412                      m && text_update_following_after_change(t, &m->ref, &pm->ref, &pm->ref);
1413                      m = doc_next_mark_all(m))
1414                         ;
1415                 text_check_consistent(t);
1416         }
1417         early = doc_prev_mark_all(pm);
1418         if (early && !mark_same(&t->doc, early, pm))
1419                 early = NULL;
1420
1421         if (str) {
1422                 struct doc_ref start;
1423                 struct mark *m;
1424
1425                 text_add_str(t, &pm->ref, str, &start, &first);
1426                 for (m = doc_prev_mark_all(pm);
1427                      m && text_update_prior_after_change(t, &m->ref, &start, &pm->ref);
1428                      m = doc_prev_mark_all(m))
1429                         ;
1430                 for (m = doc_next_mark_all(pm);
1431                      m && text_update_following_after_change(t, &m->ref, &start, &pm->ref);
1432                      m = doc_next_mark_all(m))
1433                         ;
1434                 text_check_consistent(t);
1435
1436         }
1437         doc_notify_change(&t->doc, pm, early);
1438         return first ? 1 : 2;
1439 }
1440
1441
1442 static char *__text_get_attr(struct doc *d, struct mark *m,
1443                            bool forward, char *attr)
1444 {
1445         struct text_chunk *c;
1446         struct text *t = container_of(d, struct text, doc);
1447         int o;
1448
1449         if (!m) {
1450                 char *a = attr_get_str(d->attrs, attr, -1);
1451                 if (a)
1452                         return a;
1453                 if (strcmp(attr, "default-renderer") == 0) {
1454 //                      if (t->fname && strcmp(t->fname + strlen(t->fname)-3, ".md") == 0)
1455 //                              return "present";
1456                         return "lines";
1457                 }
1458                 if (strcmp(attr, "filename") == 0)
1459                         return t->fname;
1460                 return NULL;
1461         }
1462
1463
1464         c = m->ref.c;
1465         o = m->ref.o;
1466         if (forward) {
1467                 if (!c)
1468                         /* EOF */
1469                         return NULL;
1470                 if (o >= c->end) {
1471                         /* End of chunk, need to look at next */
1472                         if (c->lst.next == &t->text)
1473                                 return NULL;
1474                         c = list_next_entry(c, lst);
1475                         o = c->start;
1476                 }
1477         } else {
1478                 if (!c) {
1479                         if (list_empty(&t->text))
1480                                 return NULL;
1481                         c = list_entry(t->text.prev, struct text_chunk, lst);
1482                         o = c->end;
1483                 }
1484                 if (o == 0) {
1485                         if (c->lst.prev == &t->text)
1486                                 return NULL;
1487                         c = list_entry(c->lst.prev, struct text_chunk, lst);
1488                         o = c->end;
1489                 }
1490                 o -= 1;
1491         }
1492         return attr_get_str(c->attrs, attr, o);
1493 }
1494
1495 DEF_CMD(text_get_attr)
1496 {
1497         struct doc_data *dd = ci->home->data;
1498         struct mark *m = ci->mark;
1499         bool forward = ci->numeric != 0;
1500         char *attr = ci->str;
1501         char *val = __text_get_attr(dd->doc, m, forward, attr);
1502
1503         comm_call(ci->comm2, "callback:get_attr", ci->focus, 0, NULL, val, 0);
1504         return 1;
1505 }
1506
1507 DEF_CMD(text_set_attr)
1508 {
1509         char *attr = ci->str;
1510         char *val = ci->str2;
1511         struct text_chunk *c = ci->mark->ref.c;
1512         struct doc_data *dd = ci->home->data;
1513         struct text *t = container_of(dd->doc, struct text, doc);
1514         int o = ci->mark->ref.o;
1515
1516         if (!c)
1517                 /* EOF */
1518                 return -1;
1519         if (o >= c->end) {
1520                 /* End of chunk, need to look at next */
1521                 if (c->lst.next == &t->text)
1522                         return -1;
1523                 c = list_next_entry(c, lst);
1524                 o = c->start;
1525         }
1526         doc_notify_change(&t->doc, ci->mark, NULL);
1527         return attr_set_str(&c->attrs, attr, val, o);
1528 }
1529
1530 DEF_CMD(text_destroy)
1531 {
1532         struct doc_data *dd = ci->home->data;
1533         struct text *t = container_of(dd->doc, struct text, doc);
1534
1535         while (!list_empty(&t->text)) {
1536                 struct text_chunk *c = list_entry(t->text.next, struct text_chunk, lst);
1537                 list_del(&c->lst);
1538                 attr_free(&c->attrs);
1539                 free(c);
1540         }
1541         while (t->alloc) {
1542                 struct text_alloc *ta = t->alloc;
1543                 t->alloc = ta->prev;
1544                 free(ta);
1545         }
1546         while (t->undo) {
1547                 struct text_edit *te = t->undo;
1548                 t->undo = te->next;
1549                 free(te);
1550         }
1551         while (t->redo) {
1552                 struct text_edit *te = t->redo;
1553                 t->redo = te->next;
1554                 free(te);
1555         }
1556         free(t->fname);
1557         return 1;
1558 }
1559
1560 #define LARGE_LINE 4096
1561
1562 DEF_CMD(render_line_prev)
1563 {
1564         /* In the process of rendering a line we need to find the
1565          * start of line.
1566          * Search backwards until a newline or start-of-file is found,
1567          * or until a LARGE_LINE boundary has been passed and a further
1568          * LARGE_LINE/2 bytes examined with no newline. In that case,
1569          * report the boundary.
1570          * If RPT_NUM == 1, step back at least one character so we get
1571          * the previous line and not the line we are on.
1572          * If we hit start-of-file without finding newline, return -1;
1573          */
1574         struct mark *m = ci->mark;
1575         struct doc_data *dd = ci->home->data;
1576         struct doc *d = dd->doc;
1577         struct mark *boundary = NULL;
1578         int since_boundary;
1579         int rpt = RPT_NUM(ci);
1580         wint_t ch;
1581         int offset = 0;
1582
1583         while ((ch = mark_prev(d, m)) != WEOF &&
1584                (ch != '\n' || rpt > 0) &&
1585                (!boundary || since_boundary < LARGE_LINE/2)) {
1586                 rpt = 0;
1587                 if (boundary)
1588                         since_boundary += 1;
1589                 else if (m->ref.o < offset &&
1590                          m->ref.o >= LARGE_LINE &&
1591                          (m->ref.o-1) / LARGE_LINE != (offset-1) / LARGE_LINE) {
1592                         /* here is a boundary */
1593                         boundary = mark_dup(m, 1);
1594                 }
1595                 offset = m->ref.o;
1596         }
1597         if (ch != WEOF && ch != '\n') {
1598                 /* need to use the boundary */
1599                 if (!boundary)
1600                         return 1;
1601                 mark_to_mark(m, boundary);
1602                 mark_free(boundary);
1603                 return 1;
1604         }
1605         if (boundary)
1606                 mark_free(boundary);
1607         if (ch == WEOF && rpt)
1608                 return -2;
1609         if (ch == '\n')
1610                 /* Found a '\n', so step back over it for start-of-line. */
1611                 mark_next(d, m);
1612         return 1;
1613 }
1614
1615 DEF_CMD(render_line)
1616 {
1617         /* Render the line from 'mark' to the first '\n' or until
1618          * 'extra' chars.
1619          * Convert '<' to '<<' and if a char has the 'highlight' attribute,
1620          * include that between '<>'.
1621          */
1622         struct buf b;
1623         struct doc_data *dd = ci->home->data;
1624         struct doc *d = dd->doc;
1625         struct mark *m = ci->mark;
1626         struct mark *pm = ci->mark2; /* The location to render as focus */
1627         int o = ci->numeric;
1628         wint_t ch = WEOF;
1629         int chars = 0;
1630         int ret;
1631
1632         if (!m)
1633                 return -1;
1634
1635         buf_init(&b);
1636         while (1) {
1637                 char *attr = __text_get_attr(d, m, 1, "highlight");
1638                 int offset = m->ref.o;
1639                 if (o >= 0 && b.len >= o)
1640                         break;
1641                 if (pm && mark_same(d, m, pm))
1642                         break;
1643                 ch = mark_next(d, m);
1644                 if (ch == WEOF)
1645                         break;
1646                 if (ch == '\n') {
1647                         buf_append(&b, ch);
1648                         break;
1649                 }
1650                 if (chars > LARGE_LINE/2 &&
1651                     m->ref.o > offset &&
1652                     (m->ref.o-1)/LARGE_LINE != (offset-1)/LARGE_LINE)
1653                         break;
1654                 if (attr) {
1655                         buf_append(&b, '<');
1656                         buf_concat(&b, attr);
1657                         buf_append(&b, '>');
1658                 }
1659                 if (ch == '<') {
1660                         if (o >= 0 && b.len+1 >= o) {
1661                                 mark_prev(d, m);
1662                                 break;
1663                         }
1664                         buf_append(&b, '<');
1665                 }
1666                 if (ch < ' ' && ch != '\t' && ch != '\n') {
1667                         buf_concat(&b, "<fg:red>^");
1668                         buf_append(&b, '@' + ch);
1669                         buf_concat(&b, "</>");
1670                 } else if (ch == 0x7f) {
1671                         buf_concat(&b, "<fg:red>^?</>");
1672                 } else
1673                         buf_append(&b, ch);
1674                 if (attr)
1675                         buf_concat(&b, "</>");
1676                 chars++;
1677         }
1678         ret = comm_call(ci->comm2, "callback:render", ci->focus, 0, NULL,
1679                         buf_final(&b), 0);
1680         free(b.b);
1681         return ret;
1682 }
1683
1684 void edlib_init(struct editor *ed)
1685 {
1686         key_add(ed->commands, "doc-text", &text_new);
1687
1688         text_map = key_alloc();
1689         key_add(text_map, "render-line-prev", &render_line_prev);
1690         key_add(text_map, "render-line", &render_line);
1691
1692         key_add(text_map, "doc:load-file", &text_load_file);
1693         key_add(text_map, "doc:same-file", &text_same_file);
1694         key_add(text_map, "doc:get-str", &text_get_str);
1695         key_add(text_map, "doc:destroy", &text_destroy);
1696         key_add(text_map, "doc:set-ref", &text_set_ref);
1697         key_add(text_map, "doc:save-file", &text_save_file);
1698         key_add(text_map, "doc:reundo", &text_reundo);
1699         key_add(text_map, "doc:set-attr", &text_set_attr);
1700         key_add(text_map, "doc:get-attr", &text_get_attr);
1701         key_add(text_map, "doc:replace", &text_replace);
1702         key_add(text_map, "doc:mark-same", &text_mark_same);
1703         key_add(text_map, "doc:step", &text_step);
1704 }