1 /* MIT (BSD) license - see LICENSE file for details */
2 #include <ccan/ungraph/ungraph.h>
3 #include <ccan/tal/str/str.h>
13 /* If it's a node, this is non-NULL */
15 /* NULL if none found, edge it one found, self if > 1 */
16 struct edge *nearest_edge;
20 struct text *src, *dst;
25 /* This means we actually found two "nearest_edge" */
26 static struct edge fake_edge;
28 #define EDGES "+/-\\|"
43 static enum dir opposite_dir(enum dir dir)
48 static enum dir clockwise(enum dir dir)
53 static enum dir anticlockwise(enum dir dir)
58 static enum dir dir_away(const struct text *t, struct xy xy)
61 enum dir dirs[3][3] = {{UP_LEFT, UP, UP_RIGHT},
62 {LEFT, INVALID, RIGHT},
63 {DOWN_LEFT, DOWN, DOWN_RIGHT}};
67 else if (xy.y > t->xy.y)
71 if (xy.x >= t->xy.x + t->width)
73 else if (xy.x < t->xy.x)
78 return dirs[ydir+1][xdir+1];
81 static char line_for_dir(enum dir dir)
102 static char arrow_for_dir(enum dir dir)
123 static struct xy move_in_dir(struct xy xy, enum dir dir)
160 static char *sqc(char **sq, struct xy xy)
162 return &sq[xy.y][xy.x];
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)
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));
181 return move_in_dir(xy, *cur);
184 static void start_perimeter(struct xy *xyp, enum dir *dirp, struct xy xy)
191 static void next_perimeter(struct xy *xyp, enum dir *dirp, struct xy xy, size_t width)
193 *xyp = move_in_dir(*xyp, *dirp);
194 if (*dirp == RIGHT && xyp->x == xy.x + width)
196 else if (*dirp == DOWN && xyp->y == xy.y + 1)
198 else if (*dirp == LEFT && xyp->x == xy.x - 1)
200 else if (*dirp == UP && xyp->y == xy.y - 2)
204 /* Useful iterators. */
205 #define for_each_scan_dir(xyp, dirp, xy, dir) \
206 for (*dirp = dir, *xyp = move_in_dir(xy, *dirp); \
208 *xyp = scan_move_next(xy, dir, dirp))
210 #define for_each_perimeter(xyp, dirp, xy, width) \
211 for (start_perimeter(xyp, dirp, xy); \
213 next_perimeter(xyp, dirp, xy, width))
215 /* Canonicalizes str into array of characters, finds text strings. */
216 static char **square(const tal_t *ctx,
220 size_t width = 0, height = 0;
223 struct text *cur_text;
226 *texts = tal_arr(ctx, struct text, 0);
229 for (size_t i = 0; str[i]; i++) {
230 if (str[i] == '\n') {
235 if (line_len > width)
241 /* If didn't end in \n, it's implied */
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);
254 /* Copy across and find text */
257 for (size_t i = 0; i < strlen; i++) {
261 eol = (str[i] == '\n' || str[i] == '\0');
263 sq[height][width] = str[i];
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;
278 cur_text->node = NULL;
279 cur_text->nearest_edge = NULL;
285 /* Trim final space */
286 if (sq[cur_text->xy.y][cur_text->xy.x + cur_text->width-1] == ' ')
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);
292 cur_text->text = tal_strndup(ctx, &sq[cur_text->xy.y][cur_text->xy.x],
310 /* If text was not previously a node, it is now! */
311 static const char *text_now_node(const tal_t *ctx,
314 void *(*add_node)(const tal_t *ctx,
322 /* Already a node? */
326 text->node = add_node(ctx, text->text, &err, arg);
332 static bool correct_line_char(char c, enum dir dir, enum dir *newdir)
334 if (c == line_for_dir(dir)) {
337 } else if (c == line_for_dir(anticlockwise(dir))) {
338 *newdir = anticlockwise(dir);
340 } else if (c == line_for_dir(clockwise(dir))) {
341 *newdir = clockwise(dir);
347 static bool seek_line(char **sq, struct xy *xy, enum dir *dir)
352 for_each_scan_dir(&scan, &scandir, *xy, *dir) {
353 if (correct_line_char(*sqc(sq, scan), scandir, &scandir))
355 /* + in front always works */
356 if (*dir == scandir && *sqc(sq, scan) == '+')
367 static bool seek_arrowhead(char **sq, struct xy *xy, enum dir *dir)
372 for_each_scan_dir(&scan, &scandir, *xy, *dir) {
373 if (strchr(ARROWS, *sqc(sq, scan))) {
382 static struct text *in_text(struct text *texts, struct xy xy)
384 for (size_t i = 0; i < tal_count(texts); i++) {
385 if (texts[i].xy.y != xy.y)
387 if (xy.x >= texts[i].xy.x + texts[i].width)
389 if (xy.x < texts[i].xy.x)
396 static struct text *seek_text(struct text *texts,
397 struct xy xy, enum dir dir)
402 for_each_scan_dir(&scan, &scandir, xy, dir) {
403 struct text *t = in_text(texts, scan);
410 static void erase_line(char **sq,
417 /* If we go straight through a +, convert for crossover */
418 if (prev_dir == dir && *sqc(sq, xy) == '+') {
419 if (dir == UP || dir == DOWN)
421 if (dir == LEFT || dir == RIGHT)
427 static bool in_nearby(struct text **nearby, const struct text *t)
429 for (size_t i = 0; i < tal_count(nearby); i++) {
436 static void add_nearby(struct text ***nearby,
442 size_t n = tal_count(*nearby);
444 for_each_perimeter(&perim, &pdir, xy, 1) {
445 struct text *t = in_text(texts, perim);
448 /* Don't care if it's already a node */
451 if (in_nearby(*nearby, t))
453 tal_resize(nearby, n+1);
458 /* Clears lines as it goes. */
459 static struct text *follow_line(char **sq,
466 struct text ***nearby)
468 char expect_arrow = arrow_for_dir(opposite_dir(dir));
471 *nearby = tal_arr(sq, struct text *, 0);
473 if (*sqc(sq, xy) == expect_arrow) {
475 } else if (*sqc(sq, xy) == line_for_dir(dir)) {
477 } else if (*sqc(sq, xy) == line_for_dir(anticlockwise(dir))) {
479 dir = anticlockwise(dir);
480 } else if (*sqc(sq, xy) == line_for_dir(clockwise(dir))) {
482 dir = clockwise(dir);
485 /* No arrow is fine. */
489 erase_line(sq, xy, dir, INVALID);
490 add_nearby(nearby, texts, xy);
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);
503 if (!*arrow_dst && seek_arrowhead(sq, &xy, &dir)) {
504 erase_line(sq, xy, dir, prev_dir);
505 add_nearby(nearby, texts, xy);
513 /* Must be in text! */
515 return seek_text(texts, xy, dir);
518 static const char *try_create_edge(const tal_t *ctx,
523 void *(*add_node)(const tal_t *ctx,
531 bool arrow_src, arrow_dst, dangling;
532 struct text **nearby;
536 if (in_text(texts, xy))
539 dst = follow_line(sq, texts, xy, dir_away(src, xy), &arrow_src, &arrow_dst, &dangling, &nearby);
542 return tal_fmt(ctx, "Found dangling arrow at (%zu,%zu)", xy.x-1, xy.y-1);
546 /* If you weren't a node before, you are now! */
547 err = text_now_node(ctx, sq, src, add_node, arg);
550 err = text_now_node(ctx, sq, dst, add_node, arg);
554 /* No arrows equiv to both arrows */
555 if (!arrow_src && !arrow_dst)
556 arrow_src = arrow_dst = true;
558 *edge = tal(NULL, struct edge);
562 (*edge)->bidir = arrow_src;
566 (*edge)->bidir = false;
568 (*edge)->labels = tal_arr(*edge, const char *, 0);
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 */
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;
580 nearby[i]->nearest_edge = *edge;
586 static const char *scan_for_unused(const tal_t *ctx,
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))
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);
603 static void add_label(struct edge *edge, const struct text *label)
605 size_t n = tal_count(edge->labels);
606 tal_resize(&edge->labels, n+1);
607 edge->labels[n] = label->text;
610 const char *ungraph_(const tal_t *ctx,
612 void *(*add_node)(const tal_t *ctx,
616 const char *(*add_edge)(const tal_t *ctx,
624 /* To hold all our temporaries! */
625 const tal_t *sub = tal(ctx, char);
627 struct text *texts, *remaining_label;
630 struct edge **edges = tal_arr(sub, struct edge *, 0);
631 size_t num_edges = 0;
633 /* We create canonical square, find texts. */
634 sq = square(sub, str, &texts);
636 /* Now search for arrows around each text, cleaning
638 for (size_t i = 0; i < tal_count(texts); i++) {
641 struct text *t = &texts[i];
643 for_each_perimeter(&perim, &pdir, t->xy, t->width) {
645 err = try_create_edge(ctx, sq, texts, perim, t, add_node, arg, &edge);
649 tal_resize(&edges, num_edges+1);
650 edges[num_edges++] = tal_steal(edges, edge);
655 /* Now attach any remaining labels */
656 for (size_t i = 0; i < tal_count(texts); i++) {
657 struct text *t = &texts[i];
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);
667 add_label(t->nearest_edge, t);
670 /* Any remaining labels must be attached to already-attached labels */
673 remaining_label = NULL;
675 for (size_t i = 0; i < tal_count(texts); i++) {
678 struct text *t = &texts[i];
680 if (t->node || t->nearest_edge)
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)
688 t->nearest_edge = neighbor->nearest_edge;
689 add_label(t->nearest_edge, t);
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);
703 err = scan_for_unused(ctx, texts, sq);
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);