git.ozlabs.org Git - ccan/blob - ccan/ungraph/ungraph.c

   1 /* MIT (BSD) license - see LICENSE file for details */
   2 #include <ccan/ungraph/ungraph.h>
   3 #include <ccan/tal/str/str.h>
   4
   5 struct xy {
   6         size_t x, y;
   7 };
   8
   9 struct text {
  10         struct xy xy;
  11         size_t width;
  12         const char *text;
  13         /* If it's a node, this is non-NULL */
  14         void *node;
  15         /* NULL if none found, edge it one found, self if > 1 */
  16         struct edge *nearest_edge;
  17 };
  18
  19 struct edge {
  20         struct text *src, *dst;
  21         bool bidir;
  22         const char **labels;
  23 };
  24
  25 /* This means we actually found two "nearest_edge" */
  26 static struct edge fake_edge;
  27
  28 #define EDGES "+/-\\|"
  29 #define ARROWS "<^>v"
  30
  31 enum dir {
  32         UP,
  33         UP_RIGHT,
  34         RIGHT,
  35         DOWN_RIGHT,
  36         DOWN,
  37         DOWN_LEFT,
  38         LEFT,
  39         UP_LEFT,
  40         INVALID,
  41 };
  42
  43 static enum dir opposite_dir(enum dir dir)
  44 {
  45         return (dir + 4) % 8;
  46 }
  47
  48 static enum dir clockwise(enum dir dir)
  49 {
  50         return (dir + 1) % 8;
  51 }
  52
  53 static enum dir anticlockwise(enum dir dir)
  54 {
  55         return (dir + 7) % 8;
  56 }
  57
  58 static enum dir dir_away(const struct text *t, struct xy xy)
  59 {
  60         int xdir, ydir;
  61         enum dir dirs[3][3] = {{UP_LEFT, UP, UP_RIGHT},
  62                                {LEFT, INVALID, RIGHT},
  63                                {DOWN_LEFT, DOWN, DOWN_RIGHT}};
  64
  65         if (xy.y < t->xy.y)
  66                 ydir = -1;
  67         else if (xy.y > t->xy.y)
  68                 ydir = 1;
  69         else
  70                 ydir = 0;
  71         if (xy.x >= t->xy.x + t->width)
  72                 xdir = 1;
  73         else if (xy.x < t->xy.x)
  74                 xdir = -1;
  75         else
  76                 xdir = 0;
  77
  78         return dirs[ydir+1][xdir+1];
  79 }
  80
  81 static char line_for_dir(enum dir dir)
  82 {
  83         switch (dir) {
  84         case UP:
  85         case DOWN:
  86                 return '|';
  87         case UP_RIGHT:
  88         case DOWN_LEFT:
  89                 return '/';
  90         case RIGHT:
  91         case LEFT:
  92                 return '-';
  93         case DOWN_RIGHT:
  94         case UP_LEFT:
  95                 return '\\';
  96         case INVALID:
  97                 break;
  98         }
  99         abort();
 100 }
 101
 102 static char arrow_for_dir(enum dir dir)
 103 {
 104         switch (dir) {
 105         case UP:
 106         case UP_RIGHT:
 107         case UP_LEFT:
 108                 return '^';
 109         case DOWN:
 110         case DOWN_RIGHT:
 111         case DOWN_LEFT:
 112                 return 'v';
 113         case LEFT:
 114                 return '<';
 115         case RIGHT:
 116                 return '>';
 117         case INVALID:
 118                 break;
 119         }
 120         abort();
 121 }
 122
 123 static struct xy move_in_dir(struct xy xy, enum dir dir)
 124 {
 125         switch (dir) {
 126         case UP:
 127                 xy.y = xy.y - 1;
 128                 return xy;
 129         case DOWN:
 130                 xy.y = xy.y + 1;
 131                 return xy;
 132         case UP_RIGHT:
 133                 xy.x = xy.x + 1;
 134                 xy.y = xy.y - 1;
 135                 return xy;
 136         case DOWN_LEFT:
 137                 xy.x = xy.x - 1;
 138                 xy.y = xy.y + 1;
 139                 return xy;
 140         case RIGHT:
 141                 xy.x = xy.x + 1;
 142                 return xy;
 143         case LEFT:
 144                 xy.x = xy.x - 1;
 145                 return xy;
 146         case DOWN_RIGHT:
 147                 xy.x = xy.x + 1;
 148                 xy.y = xy.y + 1;
 149                 return xy;
 150         case UP_LEFT:
 151                 xy.x = xy.x - 1;
 152                 xy.y = xy.y - 1;
 153                 return xy;
 154         case INVALID:
 155                 break;
 156         }
 157         abort();
 158 }
 159
 160 static char *sqc(char **sq, struct xy xy)
 161 {
 162         return &sq[xy.y][xy.x];
 163 }
 164
 165 /* Try straight ahead first, then a bit to either side, then
 166  * finally left and right */
 167 static struct xy scan_move_next(struct xy xy, enum dir start, enum dir *cur)
 168 {
 169         if (*cur == start)
 170                 *cur = clockwise(start);
 171         else if (*cur == clockwise(start))
 172                 *cur = anticlockwise(start);
 173         else if (*cur == anticlockwise(start))
 174                 *cur = anticlockwise(anticlockwise(start));
 175         else if (*cur == anticlockwise(anticlockwise(start)))
 176                 *cur = clockwise(clockwise(start));
 177         else {
 178                 *cur = INVALID;
 179                 return xy;
 180         }
 181         return move_in_dir(xy, *cur);
 182 }
 183
 184 static void start_perimeter(struct xy *xyp, enum dir *dirp, struct xy xy)
 185 {
 186         *dirp = RIGHT;
 187         xyp->x = xy.x - 1;
 188         xyp->y = xy.y - 1;
 189 }
 190
 191 static void next_perimeter(struct xy *xyp, enum dir *dirp, struct xy xy, size_t width)
 192 {
 193         *xyp = move_in_dir(*xyp, *dirp);
 194         if (*dirp == RIGHT && xyp->x == xy.x + width)
 195                 *dirp = DOWN;
 196         else if (*dirp == DOWN && xyp->y == xy.y + 1)
 197                 *dirp = LEFT;
 198         else if (*dirp == LEFT && xyp->x == xy.x - 1)
 199                 *dirp = UP;
 200         else if (*dirp == UP && xyp->y == xy.y - 2)
 201                 *dirp = INVALID;
 202 }
 203
 204 /* Useful iterators. */
 205 #define for_each_scan_dir(xyp, dirp, xy, dir)                   \
 206         for (*dirp = dir, *xyp = move_in_dir(xy, *dirp);        \
 207              *dirp != INVALID;                                  \
 208              *xyp = scan_move_next(xy, dir, dirp))
 209
 210 #define for_each_perimeter(xyp, dirp, xy, width)        \
 211         for (start_perimeter(xyp, dirp, xy);            \
 212              *dirp != INVALID;                          \
 213              next_perimeter(xyp, dirp, xy, width))
 214
 215 /* Canonicalizes str into array of characters, finds text strings. */
 216 static char **square(const tal_t *ctx,
 217                      const char *str,
 218                      struct text **texts)
 219 {
 220         size_t width = 0, height = 0;
 221         size_t line_len = 0;
 222         char **sq;
 223         struct text *cur_text;
 224         size_t strlen;
 225
 226         *texts = tal_arr(ctx, struct text, 0);
 227
 228         strlen = 0;
 229         for (size_t i = 0; str[i]; i++) {
 230                 if (str[i] == '\n') {
 231                         height++;
 232                         line_len = 0;
 233                 } else {
 234                         line_len++;
 235                         if (line_len > width)
 236                                 width = line_len;
 237                 }
 238                 strlen++;
 239         }
 240
 241         /* If didn't end in \n, it's implied */
 242         if (line_len != 0) {
 243                 height++;
 244                 strlen++;
 245         }
 246
 247         /* For analysis simplicity, create a blank border. */
 248         sq = tal_arr(ctx, char *, height + 2);
 249         for (size_t i = 0; i < height + 2; i++) {
 250                 sq[i] = tal_arr(sq, char, width + 2);
 251                 memset(sq[i], ' ', width + 2);
 252         }
 253
 254         /* Copy across and find text */
 255         cur_text = NULL;
 256         width = height = 1;
 257         for (size_t i = 0; i < strlen; i++) {
 258                 bool end_text;
 259                 bool eol;
 260
 261                 eol = (str[i] == '\n' || str[i] == '\0');
 262                 if (!eol)
 263                         sq[height][width] = str[i];
 264
 265                 /* v by itself handled separately below */
 266                 if (strchr(EDGES ARROWS "\n", str[i]) && str[i] != 'v') {
 267                         end_text = (cur_text != NULL);
 268                 } else if (cur_text) {
 269                         /* Two spaces ends text */
 270                         end_text = (str[i] == ' ' && str[i-1] == ' ') || eol;
 271                 } else if (str[i] != ' ') {
 272                         size_t num_texts = tal_count(*texts);
 273                         tal_resize(texts, num_texts+1);
 274                         cur_text = &(*texts)[num_texts];
 275                         cur_text->xy.x = width;
 276                         cur_text->xy.y = height;
 277                         cur_text->width = 0;
 278                         cur_text->node = NULL;
 279                         cur_text->nearest_edge = NULL;
 280                         end_text = false;
 281                 } else
 282                         end_text = false;
 283
 284                 if (end_text) {
 285                         /* Trim final space */
 286                         if (sq[cur_text->xy.y][cur_text->xy.x + cur_text->width-1] == ' ')
 287                                 cur_text->width--;
 288                         /* Ignore lone 'v' */
 289                         if (cur_text->width == 1 && sq[cur_text->xy.y][cur_text->xy.x] == 'v')
 290                                 tal_resize(texts, tal_count(*texts)-1);
 291                         else {
 292                                 cur_text->text = tal_strndup(ctx, &sq[cur_text->xy.y][cur_text->xy.x],
 293                                                              cur_text->width);
 294                         }
 295                         cur_text = NULL;
 296                 }
 297
 298                 if (cur_text)
 299                         cur_text->width++;
 300                 if (eol) {
 301                         height++;
 302                         width = 1;
 303                 } else
 304                         width++;
 305         }
 306
 307         return sq;
 308 }
 309
 310 /* If text was not previously a node, it is now! */
 311 static const char *text_now_node(const tal_t *ctx,
 312                                  char **sq,
 313                                  struct text *text,
 314                                  void *(*add_node)(const tal_t *ctx,
 315                                                    const char *name,
 316                                                    const char **errstr,
 317                                                    void *arg),
 318                                  void *arg)
 319 {
 320         const char *err;
 321
 322         /* Already a node? */
 323         if (text->node)
 324                 return NULL;
 325
 326         text->node = add_node(ctx, text->text, &err, arg);
 327         if (!text->node)
 328                 return err;
 329         return NULL;
 330 }
 331
 332 static bool correct_line_char(char c, enum dir dir, enum dir *newdir)
 333 {
 334         if (c == line_for_dir(dir)) {
 335                 *newdir = dir;
 336                 return true;
 337         } else if (c == line_for_dir(anticlockwise(dir))) {
 338                 *newdir = anticlockwise(dir);
 339                 return true;
 340         } else if (c == line_for_dir(clockwise(dir))) {
 341                 *newdir = clockwise(dir);
 342                 return true;
 343         }
 344         return false;
 345 }
 346
 347 static bool seek_line(char **sq, struct xy *xy, enum dir *dir)
 348 {
 349         struct xy scan;
 350         enum dir scandir;
 351
 352         for_each_scan_dir(&scan, &scandir, *xy, *dir) {
 353                 if (correct_line_char(*sqc(sq, scan), scandir, &scandir))
 354                         goto found;
 355                 /* + in front always works */
 356                 if (*dir == scandir && *sqc(sq, scan) == '+')
 357                         goto found;
 358         }
 359         return false;
 360
 361 found:
 362         *xy = scan;
 363         *dir = scandir;
 364         return true;
 365 }
 366
 367 static bool seek_arrowhead(char **sq, struct xy *xy, enum dir *dir)
 368 {
 369         struct xy scan;
 370         enum dir scandir;
 371
 372         for_each_scan_dir(&scan, &scandir, *xy, *dir) {
 373                 if (strchr(ARROWS, *sqc(sq, scan))) {
 374                         *xy = scan;
 375                         *dir = scandir;
 376                         return true;
 377                 }
 378         }
 379         return false;
 380 }
 381
 382 static struct text *in_text(struct text *texts, struct xy xy)
 383 {
 384         for (size_t i = 0; i < tal_count(texts); i++) {
 385                 if (texts[i].xy.y != xy.y)
 386                         continue;
 387                 if (xy.x >= texts[i].xy.x + texts[i].width)
 388                         continue;
 389                 if (xy.x < texts[i].xy.x)
 390                         continue;
 391                 return texts + i;
 392         }
 393         return NULL;
 394 }
 395
 396 static struct text *seek_text(struct text *texts,
 397                               struct xy xy, enum dir dir)
 398 {
 399         struct xy scan;
 400         enum dir scandir;
 401
 402         for_each_scan_dir(&scan, &scandir, xy, dir) {
 403                 struct text *t = in_text(texts, scan);
 404                 if (t)
 405                         return t;
 406         }
 407         return NULL;
 408 }
 409
 410 static void erase_line(char **sq,
 411                        struct xy xy,
 412                        enum dir dir,
 413                        enum dir prev_dir)
 414 {
 415         char c = ' ';
 416
 417         /* If we go straight through a +, convert for crossover */
 418         if (prev_dir == dir && *sqc(sq, xy) == '+') {
 419                 if (dir == UP || dir == DOWN)
 420                         c = '-';
 421                 if (dir == LEFT || dir == RIGHT)
 422                         c = '|';
 423         }
 424         *sqc(sq, xy) = c;
 425 }
 426
 427 static bool in_nearby(struct text **nearby, const struct text *t)
 428 {
 429         for (size_t i = 0; i < tal_count(nearby); i++) {
 430                 if (nearby[i] == t)
 431                         return true;
 432         }
 433         return false;
 434 }
 435
 436 static void add_nearby(struct text ***nearby,
 437                        struct text *texts,
 438                        struct xy xy)
 439 {
 440         struct xy perim;
 441         enum dir pdir;
 442         size_t n = tal_count(*nearby);
 443
 444         for_each_perimeter(&perim, &pdir, xy, 1) {
 445                 struct text *t = in_text(texts, perim);
 446                 if (!t)
 447                         continue;
 448                 /* Don't care if it's already a node */
 449                 if (t->node)
 450                         continue;
 451                 if (in_nearby(*nearby, t))
 452                         continue;
 453                 tal_resize(nearby, n+1);
 454                 (*nearby)[n++] = t;
 455         }
 456 }
 457
 458 /* Clears lines as it goes. */
 459 static struct text *follow_line(char **sq,
 460                                 struct text *texts,
 461                                 struct xy xy,
 462                                 enum dir dir,
 463                                 bool *arrow_src,
 464                                 bool *arrow_dst,
 465                                 bool *dangling,
 466                                 struct text ***nearby)
 467 {
 468         char expect_arrow = arrow_for_dir(opposite_dir(dir));
 469         enum dir prev_dir;
 470
 471         *nearby = tal_arr(sq, struct text *, 0);
 472
 473         if (*sqc(sq, xy) == expect_arrow) {
 474                 *arrow_src = true;
 475         } else if (*sqc(sq, xy) == line_for_dir(dir)) {
 476                 *arrow_src = false;
 477         } else if (*sqc(sq, xy) == line_for_dir(anticlockwise(dir))) {
 478                 *arrow_src = false;
 479                 dir = anticlockwise(dir);
 480         } else if (*sqc(sq, xy) == line_for_dir(clockwise(dir))) {
 481                 *arrow_src = false;
 482                 dir = clockwise(dir);
 483         } else {
 484                 *dangling = false;
 485                 /* No arrow is fine. */
 486                 return NULL;
 487         }
 488
 489         erase_line(sq, xy, dir, INVALID);
 490         add_nearby(nearby, texts, xy);
 491
 492         *arrow_dst = false;
 493         prev_dir = dir;
 494         for (;;) {
 495                 /* Try to continue line */
 496                 if (!*arrow_dst && seek_line(sq, &xy, &dir)) {
 497                         erase_line(sq, xy, dir, prev_dir);
 498                         add_nearby(nearby, texts, xy);
 499                         prev_dir = dir;
 500                         continue;
 501                 }
 502                 /* Look for arrow */
 503                 if (!*arrow_dst && seek_arrowhead(sq, &xy, &dir)) {
 504                         erase_line(sq, xy, dir, prev_dir);
 505                         add_nearby(nearby, texts, xy);
 506                         *arrow_dst = true;
 507                         prev_dir = dir;
 508                         continue;
 509                 }
 510                 break;
 511         }
 512
 513         /* Must be in text! */
 514         *dangling = true;
 515         return seek_text(texts, xy, dir);
 516 }
 517
 518 static const char *try_create_edge(const tal_t *ctx,
 519                                    char **sq,
 520                                    struct text *texts,
 521                                    struct xy xy,
 522                                    struct text *src,
 523                                    void *(*add_node)(const tal_t *ctx,
 524                                                      const char *name,
 525                                                      const char **errstr,
 526                                                      void *arg),
 527                                    void *arg,
 528                                    struct edge **edge)
 529 {
 530         struct text *dst;
 531         bool arrow_src, arrow_dst, dangling;
 532         struct text **nearby;
 533         const char *err;
 534
 535         *edge = NULL;
 536         if (in_text(texts, xy))
 537                 return NULL;
 538
 539         dst = follow_line(sq, texts, xy, dir_away(src, xy), &arrow_src, &arrow_dst, &dangling, &nearby);
 540         if (!dst) {
 541                 if (dangling)
 542                         return tal_fmt(ctx, "Found dangling arrow at (%zu,%zu)", xy.x-1, xy.y-1);
 543                 return NULL;
 544         }
 545
 546         /* If you weren't a node before, you are now! */
 547         err = text_now_node(ctx, sq, src, add_node, arg);
 548         if (err)
 549                 return err;
 550         err = text_now_node(ctx, sq, dst, add_node, arg);
 551         if (err)
 552                 return err;
 553
 554         /* No arrows equiv to both arrows */
 555         if (!arrow_src && !arrow_dst)
 556                 arrow_src = arrow_dst = true;
 557
 558         *edge = tal(NULL, struct edge);
 559         if (arrow_dst) {
 560                 (*edge)->src = src;
 561                 (*edge)->dst = dst;
 562                 (*edge)->bidir = arrow_src;
 563         } else {
 564                 (*edge)->src = dst;
 565                 (*edge)->dst = src;
 566                 (*edge)->bidir = false;
 567         }
 568         (*edge)->labels = tal_arr(*edge, const char *, 0);
 569
 570         /* Now record any texts it passed by, in case they're labels */
 571         for (size_t i = 0; i < tal_count(nearby); i++) {
 572                 /* We might have just made it a node */
 573                 if (nearby[i]->node)
 574                         continue;
 575                 /* Already has an edge?  Mark it as near two, to error
 576                  * later if it's a label */
 577                 if (nearby[i]->nearest_edge)
 578                         nearby[i]->nearest_edge = &fake_edge;
 579                 else
 580                         nearby[i]->nearest_edge = *edge;
 581         }
 582
 583         return NULL;
 584 }
 585
 586 static const char *scan_for_unused(const tal_t *ctx,
 587                                    struct text *texts,
 588                                    char **sq)
 589 {
 590         struct xy xy;
 591         for (xy.y = 0; xy.y < tal_count(sq); xy.y++) {
 592                 for (xy.x = 0; xy.x < tal_count(sq[xy.y]); xy.x++) {
 593                         if (in_text(texts, xy))
 594                                 continue;
 595                         if (*sqc(sq,xy) != ' ')
 596                                 return tal_fmt(ctx, "Unused '%c' at (%zu,%zu)",
 597                                                *sqc(sq, xy), xy.x-1, xy.y-1);
 598                 }
 599         }
 600         return NULL;
 601 }
 602
 603 static void add_label(struct edge *edge, const struct text *label)
 604 {
 605         size_t n = tal_count(edge->labels);
 606         tal_resize(&edge->labels, n+1);
 607         edge->labels[n] = label->text;
 608 }
 609
 610 const char *ungraph_(const tal_t *ctx,
 611                      const char *str,
 612                      void *(*add_node)(const tal_t *ctx,
 613                                        const char *name,
 614                                        const char **errstr,
 615                                        void *arg),
 616                      const char *(*add_edge)(const tal_t *ctx,
 617                                              void *source_node,
 618                                              void *dest_node,
 619                                              bool bidir,
 620                                              const char **labels,
 621                                              void *arg),
 622                      void *arg)
 623 {
 624         /* To hold all our temporaries! */
 625         const tal_t *sub = tal(ctx, char);
 626         char **sq;
 627         struct text *texts, *remaining_label;
 628         const char *err;
 629         bool progress;
 630         struct edge **edges = tal_arr(sub, struct edge *, 0);
 631         size_t num_edges = 0;
 632
 633         /* We create canonical square, find texts. */
 634         sq = square(sub, str, &texts);
 635
 636         /* Now search for arrows around each text, cleaning
 637          * as we go! */
 638         for (size_t i = 0; i < tal_count(texts); i++) {
 639                 struct xy perim;
 640                 enum dir pdir;
 641                 struct text *t = &texts[i];
 642
 643                 for_each_perimeter(&perim, &pdir, t->xy, t->width) {
 644                         struct edge *edge;
 645                         err = try_create_edge(ctx, sq, texts, perim, t, add_node, arg, &edge);
 646                         if (err)
 647                                 goto fail;
 648                         if (edge) {
 649                                 tal_resize(&edges, num_edges+1);
 650                                 edges[num_edges++] = tal_steal(edges, edge);
 651                         }
 652                 }
 653         }
 654
 655         /* Now attach any remaining labels */
 656         for (size_t i = 0; i < tal_count(texts); i++) {
 657                 struct text *t = &texts[i];
 658
 659                 if (t->node)
 660                         continue;
 661                 if (t->nearest_edge == &fake_edge) {
 662                         err = tal_fmt(ctx, "Label at (%zu,%zu) near more than one edge",
 663                                       t->xy.x-1, t->xy.y-1);
 664                         goto fail;
 665                 }
 666                 if (t->nearest_edge)
 667                         add_label(t->nearest_edge, t);
 668         }
 669
 670         /* Any remaining labels must be attached to already-attached labels */
 671         do {
 672                 progress = false;
 673                 remaining_label = NULL;
 674
 675                 for (size_t i = 0; i < tal_count(texts); i++) {
 676                         struct xy perim;
 677                         enum dir pdir;
 678                         struct text *t = &texts[i];
 679
 680                         if (t->node || t->nearest_edge)
 681                                 continue;
 682
 683                         remaining_label = t;
 684                         for_each_perimeter(&perim, &pdir, t->xy, t->width) {
 685                                 struct text *neighbor = in_text(texts, perim);
 686                                 if (!neighbor || neighbor->node || !neighbor->nearest_edge)
 687                                         continue;
 688                                 t->nearest_edge = neighbor->nearest_edge;
 689                                 add_label(t->nearest_edge, t);
 690                                 progress = true;
 691                                 break;
 692                         }
 693                 }
 694         } while (progress);
 695
 696         if (remaining_label) {
 697                 err = tal_fmt(ctx, "Label at (%zu,%zu) not near any edge",
 698                               remaining_label->xy.x-1,
 699                               remaining_label->xy.y-1);
 700                 goto fail;
 701         }
 702
 703         err = scan_for_unused(ctx, texts, sq);
 704         if (err)
 705                 goto fail;
 706
 707         /* Now add edges, complete with labels */
 708         for (size_t i = 0; i < tal_count(edges); i++) {
 709                 err = add_edge(ctx, edges[i]->src->node, edges[i]->dst->node,
 710                                edges[i]->bidir, edges[i]->labels, arg);
 711                 if (err)
 712                         goto fail;
 713         }
 714
 715         tal_free(sub);
 716         return NULL;
 717
 718 fail:
 719         tal_free(sub);
 720         return err;
 721 }