From: Rusty Russell Date: Thu, 2 Jun 2022 08:32:09 +0000 (+0930) Subject: ungraph: new module X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=4c4de2df2c65453b8ca9592ccd21ce1b50f216a7 ungraph: new module Signed-off-by: Rusty Russell --- diff --git a/ccan/ungraph/LICENSE b/ccan/ungraph/LICENSE new file mode 120000 index 00000000..2354d129 --- /dev/null +++ b/ccan/ungraph/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT \ No newline at end of file diff --git a/ccan/ungraph/_info b/ccan/ungraph/_info new file mode 100644 index 00000000..6088c5e4 --- /dev/null +++ b/ccan/ungraph/_info @@ -0,0 +1,77 @@ +#include "config.h" +#include +#include + +/** + * ungraph - extract a graph from an ASCII diagram. + * + * This code takes an ASCII diagram and converts it to a graph. + * The following things are assumed: + * 1. The input consists of \n-terminated lines + * 2. /-\|+ are used for edges. + * 3. <^>v are used for arrowheads. + * 4. + can be used to cross-over. + * 5. No arrowheads or both-ended arrowheads are shortcuts for "both ways". + * 6. Edges can turn with or without a +, by up to 90 degrees. + * 7. Edges must go from one node name to another. + * 8. Any other text is an edge label which must be next to an edge or + * another label. + * + * License: BSD-MIT + * Example: + * // Convert an ASCII graph to Graphviz dot format + * #include + * #include + * #include + * + * // Just return the name as our node. + * static void *add_node(const tal_t *ctx, + * const char *name, + * const char **errstr, + * void *unused) + * { + * return (void *)name; + * } + * + * static const char *add_edge(const tal_t *ctx, + * void *source_node, + * void *dest_node, + * bool bidir, + * const char **labels, + * void *arg) + * { + * printf("%s -> %s;\n", + * (char *)source_node, (char *)dest_node); + * if (bidir) + * printf("%s -> %s;\n", + * (char *)dest_node, (char *)source_node); + * return NULL; + * } + * + * int main(int argc, char *argv[]) + * { + * const char *graph = grab_file(NULL, argv[1], NULL), *errmsg; + * printf("digraph %s {\n", argv[1] ? argv[1] : "stdin"); + * errmsg = ungraph(NULL, graph, add_node, add_edge, NULL); + * if (errmsg) + * errx(1, "%s", errmsg); + * printf("}"); + * } + * + * Author: Rusty Russell + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/tal\n"); + printf("ccan/tal/str\n"); + printf("ccan/typesafe_cb\n"); + return 0; + } + + return 1; +} diff --git a/ccan/ungraph/test/run.c b/ccan/ungraph/test/run.c new file mode 100644 index 00000000..a9ae9be5 --- /dev/null +++ b/ccan/ungraph/test/run.c @@ -0,0 +1,140 @@ +#include +/* Include the C files directly. */ +#include +#include +#include + +static void *add_node(const tal_t *ctx, + const char *name, + const char **errstr, + char **out) +{ + tal_append_fmt(out, "add_node %s\n", (char *)name); + return (void *)tal_steal(ctx, name); +} + +static const char *add_edge(const tal_t *ctx, + void *source_node, + void *dest_node, + bool bidir, + const char **labels, + char **out) +{ + tal_append_fmt(out, "add_edge %s-%s bidir=%i\n", + (char *)source_node, + (char *)dest_node, + bidir); + for (size_t i = 0; i < tal_count(labels); i++) + tal_append_fmt(out, "- label %s\n", labels[i]); + return NULL; +} + +int main(void) +{ + const tal_t *ctx = tal(NULL, char); + char *out = tal_arrz(ctx, char, 1); + /* This is how many tests you plan to run */ + plan_tests(16); + + ok1(ungraph(ctx, + "AAA----->BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge AAA-BBB bidir=0\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + "AAA<------BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge BBB-AAA bidir=0\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + "AAA------BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge AAA-BBB bidir=1\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + "AAA<------>BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge AAA-BBB bidir=1\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + "AAA\n" + " ^ \n" + " | \n" + " | \n" + " v \n" + "BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge AAA-BBB bidir=1\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + "AAA\n" + " / \n" + "| \n" + " \\ \n" + " v \n" + " BBB\n", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge AAA-BBB bidir=0\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + "AAA\n" + " / \n" + "|xyx \n" + " \\ \n" + " v \n" + " BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_edge AAA-BBB bidir=0\n" + "- label xyx\n") == 0); + + out = tal_arrz(ctx, char, 1); + ok1(ungraph(ctx, + " AAA \n" + " | \n" + "A-+----B \n" + " | LABEL \n" + " | xyz\n" + " v \n" + " BBB", + add_node, add_edge, &out) == NULL); + ok1(strcmp(out, + "add_node AAA\n" + "add_node BBB\n" + "add_node A\n" + "add_node B\n" + "add_edge AAA-BBB bidir=0\n" + "add_edge A-B bidir=1\n" + "- label LABEL\n" + "- label xyz\n") == 0); + + tal_free(ctx); + /* This exits depending on whether all tests passed */ + return exit_status(); +} diff --git a/ccan/ungraph/ungraph.c b/ccan/ungraph/ungraph.c new file mode 100644 index 00000000..ba29d223 --- /dev/null +++ b/ccan/ungraph/ungraph.c @@ -0,0 +1,721 @@ +/* MIT (BSD) license - see LICENSE file for details */ +#include +#include + +struct xy { + size_t x, y; +}; + +struct text { + struct xy xy; + size_t width; + const char *text; + /* If it's a node, this is non-NULL */ + void *node; + /* NULL if none found, edge it one found, self if > 1 */ + struct edge *nearest_edge; +}; + +struct edge { + struct text *src, *dst; + bool bidir; + const char **labels; +}; + +/* This means we actually found two "nearest_edge" */ +static struct edge fake_edge; + +#define EDGES "+/-\\|" +#define ARROWS "<^>v" + +enum dir { + UP, + UP_RIGHT, + RIGHT, + DOWN_RIGHT, + DOWN, + DOWN_LEFT, + LEFT, + UP_LEFT, + INVALID, +}; + +static enum dir opposite_dir(enum dir dir) +{ + return (dir + 4) % 8; +} + +static enum dir clockwise(enum dir dir) +{ + return (dir + 1) % 8; +} + +static enum dir anticlockwise(enum dir dir) +{ + return (dir + 7) % 8; +} + +static enum dir dir_away(const struct text *t, struct xy xy) +{ + int xdir, ydir; + enum dir dirs[3][3] = {{UP_LEFT, UP, UP_RIGHT}, + {LEFT, INVALID, RIGHT}, + {DOWN_LEFT, DOWN, DOWN_RIGHT}}; + + if (xy.y < t->xy.y) + ydir = -1; + else if (xy.y > t->xy.y) + ydir = 1; + else + ydir = 0; + if (xy.x >= t->xy.x + t->width) + xdir = 1; + else if (xy.x < t->xy.x) + xdir = -1; + else + xdir = 0; + + return dirs[ydir+1][xdir+1]; +} + +static char line_for_dir(enum dir dir) +{ + switch (dir) { + case UP: + case DOWN: + return '|'; + case UP_RIGHT: + case DOWN_LEFT: + return '/'; + case RIGHT: + case LEFT: + return '-'; + case DOWN_RIGHT: + case UP_LEFT: + return '\\'; + case INVALID: + break; + } + abort(); +} + +static char arrow_for_dir(enum dir dir) +{ + switch (dir) { + case UP: + case UP_RIGHT: + case UP_LEFT: + return '^'; + case DOWN: + case DOWN_RIGHT: + case DOWN_LEFT: + return 'v'; + case LEFT: + return '<'; + case RIGHT: + return '>'; + case INVALID: + break; + } + abort(); +} + +static struct xy move_in_dir(struct xy xy, enum dir dir) +{ + switch (dir) { + case UP: + xy.y = xy.y - 1; + return xy; + case DOWN: + xy.y = xy.y + 1; + return xy; + case UP_RIGHT: + xy.x = xy.x + 1; + xy.y = xy.y - 1; + return xy; + case DOWN_LEFT: + xy.x = xy.x - 1; + xy.y = xy.y + 1; + return xy; + case RIGHT: + xy.x = xy.x + 1; + return xy; + case LEFT: + xy.x = xy.x - 1; + return xy; + case DOWN_RIGHT: + xy.x = xy.x + 1; + xy.y = xy.y + 1; + return xy; + case UP_LEFT: + xy.x = xy.x - 1; + xy.y = xy.y - 1; + return xy; + case INVALID: + break; + } + abort(); +} + +static char *sqc(char **sq, struct xy xy) +{ + return &sq[xy.y][xy.x]; +} + +/* Try straight ahead first, then a bit to either side, then + * finally left and right */ +static struct xy scan_move_next(struct xy xy, enum dir start, enum dir *cur) +{ + if (*cur == start) + *cur = clockwise(start); + else if (*cur == clockwise(start)) + *cur = anticlockwise(start); + else if (*cur == anticlockwise(start)) + *cur = anticlockwise(anticlockwise(start)); + else if (*cur == anticlockwise(anticlockwise(start))) + *cur = clockwise(clockwise(start)); + else { + *cur = INVALID; + return xy; + } + return move_in_dir(xy, *cur); +} + +static void start_perimeter(struct xy *xyp, enum dir *dirp, struct xy xy) +{ + *dirp = RIGHT; + xyp->x = xy.x - 1; + xyp->y = xy.y - 1; +} + +static void next_perimeter(struct xy *xyp, enum dir *dirp, struct xy xy, size_t width) +{ + *xyp = move_in_dir(*xyp, *dirp); + if (*dirp == RIGHT && xyp->x == xy.x + width) + *dirp = DOWN; + else if (*dirp == DOWN && xyp->y == xy.y + 1) + *dirp = LEFT; + else if (*dirp == LEFT && xyp->x == xy.x - 1) + *dirp = UP; + else if (*dirp == UP && xyp->y == xy.y - 2) + *dirp = INVALID; +} + +/* Useful iterators. */ +#define for_each_scan_dir(xyp, dirp, xy, dir) \ + for (*dirp = dir, *xyp = move_in_dir(xy, *dirp); \ + *dirp != INVALID; \ + *xyp = scan_move_next(xy, dir, dirp)) + +#define for_each_perimeter(xyp, dirp, xy, width) \ + for (start_perimeter(xyp, dirp, xy); \ + *dirp != INVALID; \ + next_perimeter(xyp, dirp, xy, width)) + +/* Canonicalizes str into array of characters, finds text strings. */ +static char **square(const tal_t *ctx, + const char *str, + struct text **texts) +{ + size_t width = 0, height = 0; + size_t line_len = 0; + char **sq; + struct text *cur_text; + size_t strlen; + + *texts = tal_arr(ctx, struct text, 0); + + strlen = 0; + for (size_t i = 0; str[i]; i++) { + if (str[i] == '\n') { + height++; + line_len = 0; + } else { + line_len++; + if (line_len > width) + width = line_len; + } + strlen++; + } + + /* If didn't end in \n, it's implied */ + if (line_len != 0) { + height++; + strlen++; + } + + /* For analysis simplicity, create a blank border. */ + sq = tal_arr(ctx, char *, height + 2); + for (size_t i = 0; i < height + 2; i++) { + sq[i] = tal_arr(sq, char, width + 2); + memset(sq[i], ' ', width + 2); + } + + /* Copy across and find text */ + cur_text = NULL; + width = height = 1; + for (size_t i = 0; i < strlen; i++) { + bool end_text; + bool eol; + + eol = (str[i] == '\n' || str[i] == '\0'); + if (!eol) + sq[height][width] = str[i]; + + /* v by itself handled separately below */ + if (strchr(EDGES ARROWS "\n", str[i]) && str[i] != 'v') { + end_text = (cur_text != NULL); + } else if (cur_text) { + /* Two spaces ends text */ + end_text = (str[i] == ' ' && str[i-1] == ' ') || eol; + } else if (str[i] != ' ') { + size_t num_texts = tal_count(*texts); + tal_resize(texts, num_texts+1); + cur_text = &(*texts)[num_texts]; + cur_text->xy.x = width; + cur_text->xy.y = height; + cur_text->width = 0; + cur_text->node = NULL; + cur_text->nearest_edge = NULL; + end_text = false; + } else + end_text = false; + + if (end_text) { + /* Trim final space */ + if (sq[cur_text->xy.y][cur_text->xy.x + cur_text->width-1] == ' ') + cur_text->width--; + /* Ignore lone 'v' */ + if (cur_text->width == 1 && sq[cur_text->xy.y][cur_text->xy.x] == 'v') + tal_resize(texts, tal_count(*texts)-1); + else { + cur_text->text = tal_strndup(ctx, &sq[cur_text->xy.y][cur_text->xy.x], + cur_text->width); + } + cur_text = NULL; + } + + if (cur_text) + cur_text->width++; + if (eol) { + height++; + width = 1; + } else + width++; + } + + return sq; +} + +/* If text was not previously a node, it is now! */ +static const char *text_now_node(const tal_t *ctx, + char **sq, + struct text *text, + void *(*add_node)(const tal_t *ctx, + const char *name, + const char **errstr, + void *arg), + void *arg) +{ + const char *err; + + /* Already a node? */ + if (text->node) + return NULL; + + text->node = add_node(ctx, text->text, &err, arg); + if (!text->node) + return err; + return NULL; +} + +static bool correct_line_char(char c, enum dir dir, enum dir *newdir) +{ + if (c == line_for_dir(dir)) { + *newdir = dir; + return true; + } else if (c == line_for_dir(anticlockwise(dir))) { + *newdir = anticlockwise(dir); + return true; + } else if (c == line_for_dir(clockwise(dir))) { + *newdir = clockwise(dir); + return true; + } + return false; +} + +static bool seek_line(char **sq, struct xy *xy, enum dir *dir) +{ + struct xy scan; + enum dir scandir; + + for_each_scan_dir(&scan, &scandir, *xy, *dir) { + if (correct_line_char(*sqc(sq, scan), scandir, &scandir)) + goto found; + /* + in front always works */ + if (*dir == scandir && *sqc(sq, scan) == '+') + goto found; + } + return false; + +found: + *xy = scan; + *dir = scandir; + return true; +} + +static bool seek_arrowhead(char **sq, struct xy *xy, enum dir *dir) +{ + struct xy scan; + enum dir scandir; + + for_each_scan_dir(&scan, &scandir, *xy, *dir) { + if (strchr(ARROWS, *sqc(sq, scan))) { + *xy = scan; + *dir = scandir; + return true; + } + } + return false; +} + +static struct text *in_text(struct text *texts, struct xy xy) +{ + for (size_t i = 0; i < tal_count(texts); i++) { + if (texts[i].xy.y != xy.y) + continue; + if (xy.x >= texts[i].xy.x + texts[i].width) + continue; + if (xy.x < texts[i].xy.x) + continue; + return texts + i; + } + return NULL; +} + +static struct text *seek_text(struct text *texts, + struct xy xy, enum dir dir) +{ + struct xy scan; + enum dir scandir; + + for_each_scan_dir(&scan, &scandir, xy, dir) { + struct text *t = in_text(texts, scan); + if (t) + return t; + } + return NULL; +} + +static void erase_line(char **sq, + struct xy xy, + enum dir dir, + enum dir prev_dir) +{ + char c = ' '; + + /* If we go straight through a +, convert for crossover */ + if (prev_dir == dir && *sqc(sq, xy) == '+') { + if (dir == UP || dir == DOWN) + c = '-'; + if (dir == LEFT || dir == RIGHT) + c = '|'; + } + *sqc(sq, xy) = c; +} + +static bool in_nearby(struct text **nearby, const struct text *t) +{ + for (size_t i = 0; i < tal_count(nearby); i++) { + if (nearby[i] == t) + return true; + } + return false; +} + +static void add_nearby(struct text ***nearby, + struct text *texts, + struct xy xy) +{ + struct xy perim; + enum dir pdir; + size_t n = tal_count(*nearby); + + for_each_perimeter(&perim, &pdir, xy, 1) { + struct text *t = in_text(texts, perim); + if (!t) + continue; + /* Don't care if it's already a node */ + if (t->node) + continue; + if (in_nearby(*nearby, t)) + continue; + tal_resize(nearby, n+1); + (*nearby)[n++] = t; + } +} + +/* Clears lines as it goes. */ +static struct text *follow_line(char **sq, + struct text *texts, + struct xy xy, + enum dir dir, + bool *arrow_src, + bool *arrow_dst, + bool *dangling, + struct text ***nearby) +{ + char expect_arrow = arrow_for_dir(opposite_dir(dir)); + enum dir prev_dir; + + *nearby = tal_arr(sq, struct text *, 0); + + if (*sqc(sq, xy) == expect_arrow) { + *arrow_src = true; + } else if (*sqc(sq, xy) == line_for_dir(dir)) { + *arrow_src = false; + } else if (*sqc(sq, xy) == line_for_dir(anticlockwise(dir))) { + *arrow_src = false; + dir = anticlockwise(dir); + } else if (*sqc(sq, xy) == line_for_dir(clockwise(dir))) { + *arrow_src = false; + dir = clockwise(dir); + } else { + *dangling = false; + /* No arrow is fine. */ + return NULL; + } + + erase_line(sq, xy, dir, INVALID); + add_nearby(nearby, texts, xy); + + *arrow_dst = false; + prev_dir = dir; + for (;;) { + /* Try to continue line */ + if (!*arrow_dst && seek_line(sq, &xy, &dir)) { + erase_line(sq, xy, dir, prev_dir); + add_nearby(nearby, texts, xy); + prev_dir = dir; + continue; + } + /* Look for arrow */ + if (!*arrow_dst && seek_arrowhead(sq, &xy, &dir)) { + erase_line(sq, xy, dir, prev_dir); + add_nearby(nearby, texts, xy); + *arrow_dst = true; + prev_dir = dir; + continue; + } + break; + } + + /* Must be in text! */ + *dangling = true; + return seek_text(texts, xy, dir); +} + +static const char *try_create_edge(const tal_t *ctx, + char **sq, + struct text *texts, + struct xy xy, + struct text *src, + void *(*add_node)(const tal_t *ctx, + const char *name, + const char **errstr, + void *arg), + void *arg, + struct edge **edge) +{ + struct text *dst; + bool arrow_src, arrow_dst, dangling; + struct text **nearby; + const char *err; + + *edge = NULL; + if (in_text(texts, xy)) + return NULL; + + dst = follow_line(sq, texts, xy, dir_away(src, xy), &arrow_src, &arrow_dst, &dangling, &nearby); + if (!dst) { + if (dangling) + return tal_fmt(ctx, "Found dangling arrow at (%zu,%zu)", xy.x-1, xy.y-1); + return NULL; + } + + /* If you weren't a node before, you are now! */ + err = text_now_node(ctx, sq, src, add_node, arg); + if (err) + return err; + err = text_now_node(ctx, sq, dst, add_node, arg); + if (err) + return err; + + /* No arrows equiv to both arrows */ + if (!arrow_src && !arrow_dst) + arrow_src = arrow_dst = true; + + *edge = tal(NULL, struct edge); + if (arrow_dst) { + (*edge)->src = src; + (*edge)->dst = dst; + (*edge)->bidir = arrow_src; + } else { + (*edge)->src = dst; + (*edge)->dst = src; + (*edge)->bidir = false; + } + (*edge)->labels = tal_arr(*edge, const char *, 0); + + /* Now record any texts it passed by, in case they're labels */ + for (size_t i = 0; i < tal_count(nearby); i++) { + /* We might have just made it a node */ + if (nearby[i]->node) + continue; + /* Already has an edge? Mark it as near two, to error + * later if it's a label */ + if (nearby[i]->nearest_edge) + nearby[i]->nearest_edge = &fake_edge; + else + nearby[i]->nearest_edge = *edge; + } + + return NULL; +} + +static const char *scan_for_unused(const tal_t *ctx, + struct text *texts, + char **sq) +{ + struct xy xy; + for (xy.y = 0; xy.y < tal_count(sq); xy.y++) { + for (xy.x = 0; xy.x < tal_count(sq[xy.y]); xy.x++) { + if (in_text(texts, xy)) + continue; + if (*sqc(sq,xy) != ' ') + return tal_fmt(ctx, "Unused '%c' at (%zu,%zu)", + *sqc(sq, xy), xy.x-1, xy.y-1); + } + } + return NULL; +} + +static void add_label(struct edge *edge, const struct text *label) +{ + size_t n = tal_count(edge->labels); + tal_resize(&edge->labels, n+1); + edge->labels[n] = label->text; +} + +const char *ungraph_(const tal_t *ctx, + const char *str, + void *(*add_node)(const tal_t *ctx, + const char *name, + const char **errstr, + void *arg), + const char *(*add_edge)(const tal_t *ctx, + void *source_node, + void *dest_node, + bool bidir, + const char **labels, + void *arg), + void *arg) +{ + /* To hold all our temporaries! */ + const tal_t *sub = tal(ctx, char); + char **sq; + struct text *texts, *remaining_label; + const char *err; + bool progress; + struct edge **edges = tal_arr(sub, struct edge *, 0); + size_t num_edges = 0; + + /* We create canonical square, find texts. */ + sq = square(sub, str, &texts); + + /* Now search for arrows around each text, cleaning + * as we go! */ + for (size_t i = 0; i < tal_count(texts); i++) { + struct xy perim; + enum dir pdir; + struct text *t = &texts[i]; + + for_each_perimeter(&perim, &pdir, t->xy, t->width) { + struct edge *edge; + err = try_create_edge(ctx, sq, texts, perim, t, add_node, arg, &edge); + if (err) + goto fail; + if (edge) { + tal_resize(&edges, num_edges+1); + edges[num_edges++] = tal_steal(edges, edge); + } + } + } + + /* Now attach any remaining labels */ + for (size_t i = 0; i < tal_count(texts); i++) { + struct text *t = &texts[i]; + + if (t->node) + continue; + if (t->nearest_edge == &fake_edge) { + err = tal_fmt(ctx, "Label at (%zu,%zu) near more than one edge", + t->xy.x-1, t->xy.y-1); + goto fail; + } + if (t->nearest_edge) + add_label(t->nearest_edge, t); + } + + /* Any remaining labels must be attached to already-attached labels */ + do { + progress = false; + remaining_label = NULL; + + for (size_t i = 0; i < tal_count(texts); i++) { + struct xy perim; + enum dir pdir; + struct text *t = &texts[i]; + + if (t->node || t->nearest_edge) + continue; + + remaining_label = t; + for_each_perimeter(&perim, &pdir, t->xy, t->width) { + struct text *neighbor = in_text(texts, perim); + if (!neighbor || neighbor->node || !neighbor->nearest_edge) + continue; + t->nearest_edge = neighbor->nearest_edge; + add_label(t->nearest_edge, t); + progress = true; + break; + } + } + } while (progress); + + if (remaining_label) { + err = tal_fmt(ctx, "Label at (%zu,%zu) not near any edge", + remaining_label->xy.x-1, + remaining_label->xy.y-1); + goto fail; + } + + err = scan_for_unused(ctx, texts, sq); + if (err) + goto fail; + + /* Now add edges, complete with labels */ + for (size_t i = 0; i < tal_count(edges); i++) { + err = add_edge(ctx, edges[i]->src->node, edges[i]->dst->node, + edges[i]->bidir, edges[i]->labels, arg); + if (err) + goto fail; + } + + tal_free(sub); + return NULL; + +fail: + tal_free(sub); + return err; +} diff --git a/ccan/ungraph/ungraph.h b/ccan/ungraph/ungraph.h new file mode 100644 index 00000000..8480b359 --- /dev/null +++ b/ccan/ungraph/ungraph.h @@ -0,0 +1,53 @@ +/* MIT (BSD) license - see LICENSE file for details */ +#ifndef CCAN_UNGRAPH_H +#define CCAN_UNGRAPH_H +#include +#include + +/** + * ungraph: extract a graph from an ASCII graph. + * @ctx: context for callbacks, and/or returned errstr. + * @str: a string containing a graph. + * @add_node: callback for a new node, returns node. + * @add_edge: callback for a new edge, with tal_count(labels). + * @arg: callback argument. + * + * On success, returns NULL. On failure, returns some error message + * (allocated off @ctx, or returned from callbacks). + * + * If @add_node returns NULL, it must set @errstr. @add_edge + * returns the error message directly. + * + * @add_node and @add_edge can tal_steal the name/labels if they want, + * otherwise they will be freed. + */ +const char *ungraph_(const tal_t *ctx, + const char *str, + void *(*add_node)(const tal_t *ctx, + const char *name, + const char **errstr, + void *arg), + const char *(*add_edge)(const tal_t *ctx, + void *source_node, + void *dest_node, + bool bidir, + const char **labels, + void *arg), + void *arg); + +#define ungraph(ctx, str, add_node, add_edge, arg) \ + ungraph_((ctx), (str), \ + typesafe_cb_preargs(void *, void *, \ + (add_node), (arg), \ + const tal_t *, \ + const char *, \ + const char **errstr), \ + typesafe_cb_preargs(const char *, void *, \ + (add_edge), (arg), \ + const tal_t *, \ + void *, \ + void *, \ + bool, \ + const char **), \ + arg) +#endif /* CCAN_UNGRAPH_H */