/* * COPYRIGHT * * cschem - modular/flexible schematics editor - sch-rnd (executable) * Copyright (C) 2020,2022..2024 Tibor 'Igor2' Palinkas * * (Supported by NLnet NGI0 PET Fund in 2022, Entrust in 2023) * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version.* * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 31 Milk Street, # 960789 Boston, MA 02196 USA * * Contact: * Project page: http://repo.hu/projects/sch-rnd * contact lead developer: http://www.repo.hu/projects/sch-rnd/contact.html * mailing list: http://www.repo.hu/projects/sch-rnd/contact.html */ #include "config.h" #include #include #include #include #include #include "search.h" #include "operation.h" #include "cnc_line.h" #include "cnc_grp.h" #include "cnc_pen.h" #include "cnc_conn.h" #include "cnc_text.h" #include "cnc_text_dyn.h" #include #include #include "htPo.h" #include "intersect.h" #include "util_wirenet.h" int csch_wirenet_dbg_junct = 0; void csch_wirenet_recalc_obj_conn(csch_sheet_t *sheet, csch_chdr_t *wobj) { csch_recalc_obj_conn(sheet, wobj, CSCH_DSPLY_HUBTERM, CSCH_DSPLY_invalid); } void csch_wirenet_recalc_wirenet_conn(csch_sheet_t *sheet, csch_cgrp_t *grp) { htip_entry_t *e; for(e = htip_first(&grp->id2obj); e != NULL; e = htip_next(&grp->id2obj, e)) csch_wirenet_recalc_obj_conn(sheet, e->value); } typedef struct { csch_line_t *res; csch_chdr_t *ignore; g2d_vect_t pt; } find_wire_t; static csch_rtree_dir_t find_wire_cb(void *ctx_, void *obj_, const csch_rtree_box_t *box) { find_wire_t *ctx = (find_wire_t *)ctx_; csch_line_t *line = obj_; if (obj_ == ctx->ignore) return csch_RTREE_DIR_NOT_FOUND_CONT; /* accept lines that are in a wirenet */ if ((line->hdr.type == CSCH_CTYPE_LINE) && (line->hdr.parent != NULL) && (line->hdr.parent->role == CSCH_ROLE_WIRE_NET)) { /* make sure the point is really on the line (matters for diagonal lines) */ if (g2d_dist2_cline_pt(&line->inst.c, ctx->pt) < 2) { ctx->res = obj_; return csch_RTREE_DIR_FOUND_STOP; } } return csch_RTREE_DIR_NOT_FOUND_CONT; } static csch_line_t *find_wire(csch_sheet_t *sheet, csch_coord_t x, csch_coord_t y, csch_chdr_t *ignore) { find_wire_t ctx = {0}; csch_rtree_box_t query; ctx.ignore = ignore; ctx.pt.x = x; ctx.pt.y = y; query.x1 = x-2; query.y1 = y-2; query.x2 = x+2; query.y2 = y+2; csch_rtree_search_obj(&sheet->dsply[CSCH_DSPLY_WIRE], &query, find_wire_cb, &ctx); return ctx.res; } csch_line_t *csch_find_wire_at(csch_sheet_t *sheet, csch_coord_t x, csch_coord_t y, csch_chdr_t *ignore) { return find_wire(sheet, x, y, ignore); } csch_cgrp_t *csch_wirenet_new_from(csch_sheet_t *sheet, const csch_cgrp_t *attr_src) { csch_source_arg_t *src; csch_cgrp_t *grp = (csch_cgrp_t *)csch_op_create(sheet, &sheet->direct, CSCH_CTYPE_GRP); if (grp == NULL) { rnd_message(RND_MSG_ERROR, "Internal error: failed to create direct group for wirenet\n"); return NULL; } if (attr_src == NULL) { src = csch_attrib_src_c(NULL, 0, 0, "manual_draw_wirenet"); csch_attrib_set(&grp->attr, 0, "role", "wire-net", src, NULL); } else csch_attrib_copy_all(&grp->attr, &attr_src->attr); csch_cgrp_attrib_update(sheet, grp, 0, "role", "wire-net"); if (sheet->util_wirenet.recalc_inhibit) htpi_set(&sheet->util_wirenet.recalc_wn, grp, 1); return grp; } csch_cgrp_t *csch_wirenet_new(csch_sheet_t *sheet) { return csch_wirenet_new_from(sheet, NULL); } RND_INLINE void remove_grp_if_empty(csch_sheet_t *sheet, csch_cgrp_t *grp) { if ((grp == NULL) || (grp->id2obj.used != 0) || (csch_obj_is_deleted(&grp->hdr))) return; csch_op_remove(sheet, (csch_chdr_t *)grp); } /*** wire (line) merge ***/ typedef struct { csch_sheet_t *sheet; csch_line_t *self; csch_cgrp_t *wirenet; long dir; vtp0_t lines; /* list of other lines to merge */ } wire_merge_t; /* Return unique direction; 180 degree shift doesn't make a difference */ RND_INLINE long line_dir(csch_line_t *line) { double l, dx = line->inst.c.p2.x - line->inst.c.p1.x, dy = line->inst.c.p2.y - line->inst.c.p1.y; int sig, sdx, sdy; if ((dx == 0) && (dy == 0)) return 0; sdx = (dx < 0) ? -1 : +1; sdy = (dy < 0) ? -1 : +1; sig = (sdx == sdy) ? +1 : -1; l = sqrt(dx*dx + dy*dy); dx = floor(dx / l * 1000.0); dy = floor(dy / l * 1000000.0); return (dx + dy) * sig; } static csch_rtree_dir_t wire_merge_cb(void *ctx_, void *obj_, const csch_rtree_box_t *box) { wire_merge_t *ctx = ctx_; csch_line_t *line = obj_; long dir; /* must be another line in the same wirenet */ if ((line == ctx->self) || (line->hdr.type != CSCH_CTYPE_LINE) || (line->hdr.parent != ctx->wirenet)) return csch_RTREE_DIR_NOT_FOUND_CONT; /* merge only if directions match */ dir = line_dir(line); if (dir != ctx->dir) return csch_RTREE_DIR_NOT_FOUND_CONT; /* merge only if they intersect - close parallel diagonals have overlapping bbox without actual intersection shall not be merged */ if (csch_obj_intersect_obj(line->hdr.sheet, &line->hdr, &ctx->self->hdr, NULL, 0) < 1) return csch_RTREE_DIR_NOT_FOUND_CONT; vtp0_append(&ctx->lines, line); return csch_RTREE_DIR_FOUND_CONT; } void csch_wirenet_recalc_merge(csch_sheet_t *sheet, csch_line_t *line, int remove_overlap) { wire_merge_t ctx = {0}; g2d_vect_t min, max; int n, order12; csch_coord_t x1, y1, x2, y2; ctx.sheet = sheet; ctx.dir = line_dir(line); ctx.self = line; ctx.wirenet = line->hdr.parent; csch_rtree_search_obj(&sheet->dsply[CSCH_DSPLY_WIRE], &line->hdr.bbox, wire_merge_cb, &ctx); if (ctx.lines.used > 0) { /* rnd_trace("Merge #%d (%ld) with:\n", line->hdr.oid, ctx.dir);*/ if (ctx.dir == 1000) /* horizontal, use x */ order12 = (line->inst.c.p1.x < line->inst.c.p2.x); else order12 = (line->inst.c.p1.y < line->inst.c.p2.y); if (order12) { min = line->inst.c.p1; max = line->inst.c.p2; } else { min = line->inst.c.p2; max = line->inst.c.p1; } for(n = 0; n < ctx.lines.used; n++) { csch_line_t *l = ctx.lines.array[n]; if (remove_overlap) { int full_overlap = (g2d_dist2_cline_pt(&l->inst.c, line->inst.c.p1) <= 4) && (g2d_dist2_cline_pt(&l->inst.c, line->inst.c.p1) <= 4); if (full_overlap) { int trunc = 0, full = 0; /* figure which end(s) of the shorter "line" is on the longer "l" just found. Set trunc=1 only if at least one endpoint of the two lines match */ x1 = l->inst.c.p1.x; y1 = l->inst.c.p1.y; x2 = l->inst.c.p2.x; y2 = l->inst.c.p2.y; if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p1, line->inst.c.p1)) { x1 = line->inst.c.p2.x; y1 = line->inst.c.p2.y; trunc = 1; if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p2, line->inst.c.p2)) full = 1; } else if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p1, line->inst.c.p2)) { x1 = line->inst.c.p1.x; y1 = line->inst.c.p1.y; trunc = 1; if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p2, line->inst.c.p1)) full = 1; } if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p2, line->inst.c.p1)) { x2 = line->inst.c.p2.x; y2 = line->inst.c.p2.y; trunc = 1; if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p1, line->inst.c.p2)) full = 1; } else if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p2, line->inst.c.p2)) { x2 = line->inst.c.p1.x; y2 = line->inst.c.p1.y; trunc = 1; if (g2d_vect_t_eq_g2d_vect_t(l->inst.c.p2, line->inst.c.p1)) full = 1; } /* if we got here with trunc == 0, the shorter line is in the middle of the longer line and we shouldn't truncate for this overlap. (This is when no endpoint-endpoint match is found) */ if (trunc) { ctx.wirenet->wirenet_recalc_lock = 1; ctx.wirenet->wirenet_split_lock = 1; if (!full) { /* truncate l, removing the segment overlapping with "line" */ csch_cgrp_vinverse_xform(ctx.wirenet, &x1, &y1, &x2, &y2, NULL); csch_line_modify(sheet, l, &x1, &y1, &x2, &y2, 1, 0, 0); } else { /* upon full overlap, remove l */ csch_op_remove(sheet, &l->hdr); } /* remove the new "line", it's in overlap */ csch_op_remove(sheet, &line->hdr); ctx.wirenet->wirenet_recalc_lock = 0; ctx.wirenet->wirenet_split_lock = 0; csch_wirenet_recalc_junctions(sheet, ctx.wirenet); goto quit; } } } /* rnd_trace(" #%d\n", l->hdr.oid);*/ if (ctx.dir == 1000) { /* horizontal, use x */ if (l->inst.c.p1.x < min.x) min = l->inst.c.p1; if (l->inst.c.p1.x > max.x) max = l->inst.c.p1; if (l->inst.c.p2.x < min.x) min = l->inst.c.p2; if (l->inst.c.p2.x > max.x) max = l->inst.c.p2; } else { if (l->inst.c.p1.y < min.y) min = l->inst.c.p1; if (l->inst.c.p1.y > max.y) max = l->inst.c.p1; if (l->inst.c.p2.y < min.y) min = l->inst.c.p2; if (l->inst.c.p2.y > max.y) max = l->inst.c.p2; } } /* extend the new line; inverse-transform edit coords so they are in the wirenet's coord system */ x1 = min.x; y1 = min.y; x2 = max.x; y2 = max.y; ctx.wirenet->wirenet_recalc_lock = 1; ctx.wirenet->wirenet_split_lock = 1; csch_cgrp_vinverse_xform(ctx.wirenet, &x1, &y1, &x2, &y2, NULL); csch_line_modify(sheet, line, &x1, &y1, &x2, &y2, 1, 0, 0); /* remove rest of the lines */ for(n = 0; n < ctx.lines.used; n++) { csch_op_remove(sheet, ctx.lines.array[n]); /* no need to move connections: the new, extended line got all connections in csch_line_modify() above */ } ctx.wirenet->wirenet_recalc_lock = 0; ctx.wirenet->wirenet_split_lock = 0; csch_wirenet_recalc_junctions(sheet, ctx.wirenet); /* rnd_trace("final: %d;%d %d;%d\n", min.x, min.y, max.x, max.y);*/ } quit:; vtp0_uninit(&ctx.lines); } /* append group to list if not already on list; O(n^2) because we expect very few groups */ static void grp_append(vtp0_t *list, csch_cgrp_t *grp) { long n; for(n = 0; n < list->used; n++) if (list->array[n] == grp) return; vtp0_append(list, grp); } typedef struct { g2d_cline_t cline; vtp0_t *list; csch_cgrp_t *exclude_parent; } find_wire_end_t; static csch_rtree_dir_t find_wire_end_cb(void *ctx_, void *obj_, const csch_rtree_box_t *box) { find_wire_end_t *ctx = ctx_; csch_line_t *lin = obj_; if ((ctx->exclude_parent != NULL) && (lin->hdr.parent == ctx->exclude_parent)) return csch_RTREE_DIR_NOT_FOUND_CONT; if (lin->hdr.type == CSCH_CTYPE_LINE) if ((g2d_dist2_cline_pt(&ctx->cline, lin->inst.c.p1) < 2) || (g2d_dist2_cline_pt(&ctx->cline, lin->inst.c.p2) < 2)) grp_append(ctx->list, lin->hdr.parent); return csch_RTREE_DIR_NOT_FOUND_CONT; } /* append wirenet lines that end on target line */ static void find_wire_ends_on_line(csch_sheet_t *sheet, vtp0_t *list, csch_coord_t x1, csch_coord_t y1, csch_coord_t x2, csch_coord_t y2, csch_cgrp_t *exclude_wn) { csch_rtree_box_t b; find_wire_end_t ctx; ctx.list = list; ctx.cline.p1.x = x1; ctx.cline.p1.y = y1; ctx.cline.p2.x = x2; ctx.cline.p2.y = y2; ctx.exclude_parent = exclude_wn; b.x1 = G2D_MIN(x1, x2); b.y1 = G2D_MIN(y1, y2); b.x2 = G2D_MAX(x1, x2); b.y2 = G2D_MAX(y1, y2); csch_rtree_search_obj(&sheet->dsply[CSCH_DSPLY_WIRE], &b, find_wire_end_cb, &ctx); } typedef enum { /* bitfield */ MERGE_WARN_SILENT = 1, MERGE_WARN_NON_FATAL = 2 } merge_warn_t; /* A new wire line is about to be drawn (or transformed) to x1;y1 -> x2;y2. Search all wirenets that it connects and merge them returning: -1 on error 0 if no merge took place (wire goes into a new wirenet group) +1 if merges took place If return is 1, parent_out is loaded with wirenet group the new line should be part of. */ int csch_wirenet_newline_merge_parent(csch_sheet_t *sheet, csch_coord_t x1, csch_coord_t y1, csch_coord_t x2, csch_coord_t y2, csch_cgrp_t **parent_out, merge_warn_t warn, csch_chdr_t *ignore) { csch_line_t *w1, *w2; csch_cgrp_t *parent = NULL; int res = -1; vtp0_t adj_grp = {0}; /* of (csch_cgrp_t *) */ long n; /* pick up wires at the end of the new line */ w1 = find_wire(sheet, x1, y1, ignore); w2 = find_wire(sheet, x2, y2, ignore); if (w1 != NULL) grp_append(&adj_grp, w1->hdr.parent); if (w2 != NULL) grp_append(&adj_grp, w2->hdr.parent); find_wire_ends_on_line(sheet, &adj_grp, x1, y1, x2, y2, NULL); /* rnd_trace("wirenet merging: found %d adjacent groups\n", adj_grp.used);*/ if (adj_grp.used > 1) { csch_cgrp_t *g0; const char *netname = NULL; /* make sure no mistmatching net names are merged */ g0 = adj_grp.array[0]; for(n = 0; n < adj_grp.used; n++) { csch_cgrp_t *g = adj_grp.array[n]; const char *nn; if (g == NULL) continue; nn = csch_attrib_get_str(&g->attr, "name"); if (nn == NULL) continue; if (netname == NULL) { netname = nn; g0 = g; continue; } if ((strcmp(netname, nn) != 0)) { if ((warn & MERGE_WARN_SILENT) == 0) { if ((warn & MERGE_WARN_NON_FATAL) == 0) rnd_message(RND_MSG_ERROR, "Can't connect (merge) wirenets with different name: '%s' vs. '%s'\n", netname, nn); else rnd_message(RND_MSG_ERROR, "Merged wirenets with different name: '%s' vs. '%s'\n", netname, nn); } if ((warn & MERGE_WARN_NON_FATAL) == 0) goto error; } } /* rnd_trace(" merge wirenets\n");*/ parent = g0; parent->role = 0; /* disable side effects during the merge */ for(n = 0; n < adj_grp.used; n++) { csch_cgrp_t *g = adj_grp.array[n]; if ((g != NULL) && (g != g0)) { g->role = 0; csch_op_merge_into(sheet, parent, g); g->role = CSCH_ROLE_WIRE_NET; } } parent->role = CSCH_ROLE_WIRE_NET; res = 1; } else if (adj_grp.used == 1) { /* rnd_trace(" append to one existing wirenet\n"); */ parent = adj_grp.array[0]; /* append to the existing group */ res = 1; } else { /* rnd_trace(" new wirenet\n"); */ res = 0; } if (parent == NULL) goto error; for(n = 0; n < adj_grp.used; n++) { csch_cgrp_t *g = adj_grp.array[n]; remove_grp_if_empty(sheet, g); } error:; if (parent_out != NULL) *parent_out = parent; vtp0_uninit(&adj_grp); return res; } /* Get every dyntext re-rendered; useful after a forced netname change */ static void csch_wirenet_invalidate_dyntext(csch_sheet_t *sheet, csch_cgrp_t *grp) { htip_entry_t *e; for(e = htip_first(&grp->id2obj); e != NULL; e = htip_next(&grp->id2obj, e)) { csch_text_t *text = e->value; if ((text->hdr.type == CSCH_CTYPE_TEXT) && (text->dyntext)) { csch_text_dyntext_inval(text); csch_text_invalidate_font(text); } } } /* check every line of an already placed group to see if any wirenet-wirenet connection is made and merge the groups if so */ static void csch_wirenet_recalc_merges(csch_sheet_t *sheet, csch_cgrp_t *grp) { htip_entry_t *e; vtp0_t adj_grp = {0}; /* of (csch_cgrp_t *) */ long n; assert(grp->role == CSCH_ROLE_WIRE_NET); for(e = htip_first(&grp->id2obj); e != NULL; e = htip_next(&grp->id2obj, e)) { csch_line_t *lin = e->value, *w1, *w2; if (lin->hdr.type != CSCH_CTYPE_LINE) continue; w1 = find_wire(sheet, lin->inst.c.p1.x, lin->inst.c.p1.y, &lin->hdr); w2 = find_wire(sheet, lin->inst.c.p2.x, lin->inst.c.p2.y, &lin->hdr); if ((w1 != NULL) && (w1->hdr.parent != grp)) grp_append(&adj_grp, w1->hdr.parent); if ((w2 != NULL) && (w2->hdr.parent != grp)) grp_append(&adj_grp, w2->hdr.parent); find_wire_ends_on_line(sheet, &adj_grp, lin->inst.c.p1.x, lin->inst.c.p1.y, lin->inst.c.p2.x, lin->inst.c.p2.y, grp); } rnd_trace("-- grp merges for wirenet #%ld:\n", grp->hdr.oid); if (adj_grp.used > 0) { const char *old_name = csch_attrib_get_str(&grp->attr, "name"); const char *new_name = NULL, *final_name = old_name; int num_names = (old_name == NULL) ? 0 : 1; vtp0_t newos = {0}; /* figure number of names and new name, if needed */ for(n = 0; n < adj_grp.used; n++) { csch_cgrp_t *agrp = adj_grp.array[n]; const char *name; if (agrp == NULL) continue; name = csch_attrib_get_str(&agrp->attr, "name"); if (name == NULL) continue; if (final_name == NULL) new_name = final_name = name; num_names++; if ((num_names > 1) && (strcmp(name, final_name) != 0)) rnd_message(RND_MSG_ERROR, "Have to replace netname '%s' with '%s' due to network merge\n", name, final_name); } grp->role = 0; /* disable side effects during the merge */ for(n = 0; n < adj_grp.used; n++) { csch_cgrp_t *agrp = adj_grp.array[n]; if (agrp == NULL) continue; rnd_trace(" #%ld\n", agrp->hdr.oid); agrp->role = 0; csch_op_merge_into_remember(sheet, grp, agrp, &newos); agrp->role = CSCH_ROLE_WIRE_NET; if (agrp->hdr.parent != NULL) csch_op_remove(sheet, &agrp->hdr); } grp->role = CSCH_ROLE_WIRE_NET; /* revisit each object merged from adj grp, there may be overlapping lines, those didn't get merged because we disabled side effects */ for(n = 0; n < newos.used; n++) { csch_chdr_t *line = newos.array[n]; if (line->type == CSCH_CTYPE_LINE) csch_wirenet_recalc_merge(sheet, (csch_line_t *)line, 0); } vtp0_uninit(&newos); if (new_name != NULL) { csch_source_arg_t *src = csch_attrib_src_c(NULL, 0, 0, "graphical network merge"); csch_attrib_set(&grp->attr, 0, "name", new_name, src, NULL); csch_wirenet_invalidate_dyntext(sheet, grp); } csch_wirenet_recalc_junctions(sheet, grp); csch_wirenet_recalc_wirenet_conn(sheet, grp); } vtp0_uninit(&adj_grp); } typedef struct { csch_line_t *res; g2d_vect_t p1, p2; } find_existing_t; static csch_rtree_dir_t find_existing_cb(void *ctx_, void *obj_, const csch_rtree_box_t *box) { find_existing_t *ctx = (find_existing_t *)ctx_; csch_line_t *line = obj_; /* accept lines that are in a wirenet */ if ((line->hdr.type == CSCH_CTYPE_LINE) && (line->hdr.parent != NULL) && (line->hdr.parent->role == CSCH_ROLE_WIRE_NET)) { /* accept only if both endpoints of the new line is on the existing line */ if ((g2d_dist2_cline_pt(&line->inst.c, ctx->p1) < 4) && (g2d_dist2_cline_pt(&line->inst.c, ctx->p2) < 4)) { ctx->res = line; return csch_RTREE_DIR_FOUND_STOP; } } return csch_RTREE_DIR_NOT_FOUND_CONT; } static csch_line_t *csch_wirenet_find_existing(csch_sheet_t *sheet, csch_coord_t x1, csch_coord_t y1, csch_coord_t x2, csch_coord_t y2) { find_existing_t ctx; csch_rtree_box_t query; ctx.res = NULL; ctx.p1.x = x1; ctx.p1.y = y1; ctx.p2.x = x2; ctx.p2.y = y2; query.x1 = RND_MIN(x1, x2)-2; query.y1 = RND_MIN(y1, y2)-2; query.x2 = RND_MAX(x1, x2)+2; query.y2 = RND_MAX(y1, y2)+2; csch_rtree_search_obj(&sheet->dsply[CSCH_DSPLY_WIRE], &query, find_existing_cb, &ctx); return ctx.res; } csch_line_t *csch_wirenet_draw_line_in(csch_sheet_t *sheet, csch_cgrp_t *parent, csch_comm_str_t stroke_name, csch_coord_t x1, csch_coord_t y1, csch_coord_t x2, csch_coord_t y2) { csch_line_t *line; /* transform the coords of the new line to undo the parent group's transformations */ csch_cgrp_vinverse_xform(parent, &x1, &y1, NULL); csch_cgrp_vinverse_xform(parent, &x2, &y2, NULL); line = (csch_line_t *)csch_op_create(sheet, parent, CSCH_CTYPE_LINE); line->spec.p1.x = x1; line->spec.p1.y = y1; line->spec.p2.x = x2; line->spec.p2.y = y2; line->hdr.stroke_name = stroke_name; csch_line_update(sheet, line, 1); csch_cgrp_bbox_update(sheet, parent); return line; } csch_chdr_t *csch_wirenet_draw(csch_sheet_t *sheet, csch_comm_str_t stroke_name, csch_coord_t x1, csch_coord_t y1, csch_coord_t x2, csch_coord_t y2) { csch_line_t *line; csch_cgrp_t *parent; int merge_res; uundo_freeze_serial(&sheet->undo); /* do not draw a wire that's already drawn: full or partial overlap with existing line without extending it */ line = csch_wirenet_find_existing(sheet, x1, y1, x2, y2); if (line != NULL) { uundo_unfreeze_serial(&sheet->undo); rnd_message(RND_MSG_WARNING, "not drawing new wire that fully overlaps with existing wire\n"); return NULL; } merge_res = csch_wirenet_newline_merge_parent(sheet, x1, y1, x2, y2, &parent, 0, NULL); if (merge_res < 0) { uundo_unfreeze_serial(&sheet->undo); uundo_inc_serial(&sheet->undo); return NULL; } if (parent == NULL) parent = csch_wirenet_new(sheet); if (parent == NULL) return NULL; line = csch_wirenet_draw_line_in(sheet, parent, stroke_name, x1, y1, x2, y2); if (merge_res > 0) { int lock_save = parent->wirenet_split_lock; /* no split possible by drawing a new line; without disabling it, line ptr can change and that will break the calls below. Example: work/bug_files/merge* @ r6498 where recalc_merge() fails because line already has parent==NULL because recalc_junction() temporarily broke up the net */ parent->wirenet_split_lock = 1; csch_wirenet_recalc_junctions(sheet, parent); parent->wirenet_split_lock = lock_save; } csch_wirenet_recalc_obj_conn(sheet, &line->hdr); csch_wirenet_recalc_merge(sheet, line, 0); /* must be the last */ uundo_unfreeze_serial(&sheet->undo); uundo_inc_serial(&sheet->undo); return &line->hdr; } typedef struct { htPo_t jl; /* junction list */ htpi_t obj2seg; /* assigns an unique segment ID to each object */ int seg_next; /* next segment ID to use */ unsigned has_segmap:1; } crmap_t; RND_INLINE void map_seg_obj(crmap_t *map, csch_chdr_t *obj) { csch_line_t *l = (csch_line_t *)obj; if (obj->type != CSCH_CTYPE_LINE) { if (obj->type == CSCH_CTYPE_TEXT) { /* normal case: typically a netname floater */ } else rnd_message(RND_MSG_ERROR, "Internal error: non-line objects as wirenet seg is not yet supported\n"); return; } htpi_set(&map->obj2seg, l, map->seg_next); map->seg_next++; } RND_INLINE void map_seg_cr(crmap_t *map, csch_line_t *lo, csch_line_t *lp, int segmap_lp_junction, int lp_is_junc) { int id_lo, id_lp; id_lo = htpi_get(&map->obj2seg, lo); id_lp = htpi_get(&map->obj2seg, lp); if ((id_lo == 0) && (id_lp == 0)) { /* neither object of the pair has a segment ID yet */ htpi_set(&map->obj2seg, lo, map->seg_next); if (segmap_lp_junction || !lp_is_junc) htpi_set(&map->obj2seg, lp, map->seg_next); map->seg_next++; } else if ((id_lo != 0) && (id_lp != 0)) { /* both have segment IDs but they are different; renumber lp's to match lo's */ htpi_entry_t *e; for(e = htpi_first(&map->obj2seg); e != NULL; e = htpi_next(&map->obj2seg, e)) { if (e->value == id_lp) e->value = id_lo; } } else if (id_lo != 0) { if (segmap_lp_junction || !lp_is_junc) htpi_set(&map->obj2seg, lp, id_lo); } else if (id_lp != 0) htpi_set(&map->obj2seg, lo, id_lp); } static void map_wirenet_crossings(crmap_t *map, csch_sheet_t *sheet, csch_cgrp_t *wirenet, int enable_segmap, int segmap_junctions, int map_misc) { htip_entry_t *e; htPo_key_t jk; htPo_value_t jv; htPo_init(&map->jl, htPo_keyhash, htPo_keyeq); if (enable_segmap) { map->seg_next = 1; htpi_init(&map->obj2seg, ptrhash, ptrkeyeq); map->has_segmap = 1; } else map->has_segmap = 0; if (csch_wirenet_dbg_junct) rnd_trace("^^^ map_wirenet_crossings\n"); for(e = htip_first(&wirenet->id2obj); e != NULL; e = htip_next(&wirenet->id2obj, e)) { csch_chdr_t *obj = e->value; int junc = csch_obj_is_junction(obj); if (csch_wirenet_dbg_junct) rnd_trace(" obj ID=#%ld junc=%d", obj->oid, junc); if (obj->type == CSCH_CTYPE_LINE) { csch_line_t *lin = e->value; if (csch_wirenet_dbg_junct) rnd_trace(" {%ld %ld %ld %ld}", lin->inst.c.p1.x, lin->inst.c.p1.y, lin->inst.c.p2.x, lin->inst.c.p2.y); } if (csch_wirenet_dbg_junct) rnd_trace("\n"); if (junc) { /* verify if an existing junction is still valid */ jk.x = (obj->bbox.x1 + obj->bbox.x2)/2; jk.y = (obj->bbox.y1 + obj->bbox.y2)/2; jv = htPo_get(&map->jl, jk); jv.ptr = obj; htPo_set(&map->jl, jk, jv); } else if (obj->type == CSCH_CTYPE_LINE) { /* look for crossings */ csch_rtree_it_t it; csch_chdr_t *pair; for(pair = csch_rtree_first(&it, &obj->sheet->dsply[CSCH_DSPLY_WIRE], &obj->bbox); pair != NULL; pair = csch_rtree_next(&it)) { csch_line_t *lo = (csch_line_t *)obj, *lp = (csch_line_t *)pair; g2d_vect_t ip[2] = {0}; g2d_offs_t offs[2] = {-5, -5}; int n, len; int lp_is_junc; if ((pair == obj) || (pair->type != CSCH_CTYPE_LINE) || (pair->parent != wirenet)) continue; len = g2d_iscp_cline_cline(&lo->inst.c, &lp->inst.c, ip, offs); /* all junction coords are in sheet coord system because of bboxes */ lp_is_junc = csch_obj_is_junction(&lp->hdr); if (csch_wirenet_dbg_junct) rnd_trace(" junc isc len=%d\n", len); for(n = 0; n < len; n++) { jk.x = ip[n].x; jk.y = ip[n].y; jv = htPo_get(&map->jl, jk); if (!lp_is_junc) jv.i++; if ((offs[n] > 0) && (offs[n] < 1) && !lp_is_junc && (line_dir(lo) != line_dir(lp))) jv.i++; /* mid-point crossing should have a junction even for only 2 participants */ if (jv.wire == NULL) jv.wire = lo; if (csch_wirenet_dbg_junct) rnd_trace(" [%d] junc find: %ld %ld i=%d\n", n, jk.x,jk.y, jv.i); htPo_set(&map->jl, jk, jv); if (enable_segmap) map_seg_cr(map, lo, lp, segmap_junctions, lp_is_junc); } } } else if (map_misc) htpi_set(&map->obj2seg, obj, -1); if (enable_segmap) { if (segmap_junctions || !junc) { /* start a new segment for lo if it didn't cross anything */ if (htpi_get(&map->obj2seg, obj) == 0) map_seg_obj(map, obj); } } } } static void map_uninit(crmap_t *map) { htPo_uninit(&map->jl); if (map->has_segmap) htpi_uninit(&map->obj2seg); } /* There may be non-line objects, typically floaters, placed around the net, not participating in the connectivity; they are in seg -1 after the mapping. Put each in the seg they are closest to */ static void map_misc_to_closest(crmap_t *map) { htpi_entry_t *e, *e2; for(e = htpi_first(&map->obj2seg); e != NULL; e = htpi_next(&map->obj2seg, e)) { int oseg = e->value; csch_chdr_t *obj = e->key; double best_score = -1, d2; g2d_vect_t org; if (oseg >= 0) continue; switch(obj->type) { case CSCH_CTYPE_TEXT: org.x = ((csch_text_t *)obj)->inst1.x; org.y = ((csch_text_t *)obj)->inst1.y; break; default: org.x = (obj->bbox.x1 + obj->bbox.x2)/2; org.y = (obj->bbox.y1 + obj->bbox.y2)/2; } for(e2 = htpi_first(&map->obj2seg); e2 != NULL; e2 = htpi_next(&map->obj2seg, e2)) { int seg = e2->value; csch_line_t *cand = e2->key; if (seg < 0) continue; if (cand->hdr.type != CSCH_CTYPE_LINE) continue; d2 = g2d_dist2_cline_pt(&cand->inst.c, org); if ((best_score < 0) || (d2 < best_score)) { best_score = d2; e->value = seg; } } } } /* Returns 1 if the map actually using multiple segments */ static int map_is_multiseg(crmap_t *map) { htpi_entry_t *e; int first_seg = -1; for(e = htpi_first(&map->obj2seg); e != NULL; e = htpi_next(&map->obj2seg, e)) { int seg = e->value; if (seg < 0) continue; if (first_seg >= 0) { if (seg != first_seg) return 1; } else first_seg = seg; } return 0; } void csch_wirenet_recalc_junctions(csch_sheet_t *sheet, csch_cgrp_t *wirenet) { crmap_t map; htPo_entry_t *je; if (sheet->util_wirenet.recalc_inhibit) { htpi_set(&sheet->util_wirenet.recalc_wn, wirenet, 1); return; } if (wirenet->wirenet_recalc_lock) return; wirenet->wirenet_recalc_lock = 1; map_wirenet_crossings(&map, sheet, wirenet, 1, 1, 1); if (csch_wirenet_dbg_junct) rnd_trace("^^^ junctions wirenet=#%ld:\n", wirenet->hdr.oid); for(je = htPo_first(&map.jl); je != NULL; je = htPo_next(&map.jl, je)) { if (csch_wirenet_dbg_junct) rnd_trace(" %ld;%ld [%d] %p\n", je->key.x, je->key.y, je->value.i, je->value.ptr); if ((je->value.i > 2) && (je->value.ptr == NULL)) { int wseg; csch_coord_t x1, y1, x2, y2; csch_chdr_t *wire; csch_line_t *line = (csch_line_t *)csch_op_create(sheet, wirenet, CSCH_CTYPE_LINE); if (csch_wirenet_dbg_junct) rnd_trace(" create at %ld %ld\n", je->key.x, je->key.y); /* all junction coords are in sheet coord system because of bboxes */ x1 = x2 = je->key.x; y1 = y2 = je->key.y; csch_cgrp_vinverse_xform(wirenet, &x1, &y1, &x2, &y2, NULL); line->spec.p1.x = line->spec.p2.x = x1; line->spec.p1.y = line->spec.p2.y = y1; /* create the junction */ line->hdr.stroke_name = sheet->junction_pen_name; csch_line_update(sheet, line, 1); csch_cgrp_bbox_update(sheet, wirenet); /* copy a random participant wire's segment as the new junction's segment */ wire = je->value.wire; wseg = htpi_get(&map.obj2seg, wire); if (wseg != 0) htpi_set(&map.obj2seg, line, wseg); else rnd_message(RND_MSG_ERROR, "Internal error: new junction has no segment"); } else if ((je->value.i < 3) && (je->value.ptr != NULL)) { if (csch_wirenet_dbg_junct) rnd_trace(" remove at %ld %ld\n", je->key.x, je->key.y); csch_op_remove(sheet, je->value.ptr); } } if (csch_wirenet_dbg_junct) rnd_trace("SegS: %d\n", map.seg_next); if (map_is_multiseg(&map)) { /* pick up floaters */ map_misc_to_closest(&map); /* if we have more than one segments, that means the wirenet broke up; create new wirenets for each segment and move objects into them */ if (!wirenet->wirenet_split_lock && (map.seg_next > 2)) { htpi_entry_t *e; csch_cgrp_t **new_seg = calloc(sizeof(csch_cgrp_t *), map.seg_next); /* seg 0 is not used by the mapper; seg 1 is the segment we keep as original; from 2 up are the new segments (allocated on request) */ for(e = htpi_first(&map.obj2seg); e != NULL; e = htpi_next(&map.obj2seg, e)) { int seg = e->value; csch_chdr_t *obj = e->key; if ((seg > 1) && (!csch_obj_is_deleted(obj))) { if (csch_wirenet_dbg_junct) rnd_trace(" obj move #%ld/%p -> %d\n", obj->oid, obj, seg); if (new_seg[seg] == NULL) { new_seg[seg] = csch_wirenet_new_from(sheet, wirenet); new_seg[seg]->hdr.selected = wirenet->hdr.selected; } csch_op_move_into(sheet, new_seg[seg], obj, 0, 0); } } free(new_seg); } remove_grp_if_empty(sheet, wirenet); } map_uninit(&map); wirenet->wirenet_recalc_lock = 0; } /* Recalculate junctions of a wirenet and remove the wirenet if it became empty */ RND_INLINE void wirenet_remove_or_recalc(csch_sheet_t *sheet, csch_cgrp_t *wirenet) { csch_wirenet_recalc_junctions(sheet, wirenet); if (!csch_obj_is_deleted(&wirenet->hdr)) if (htip_first(&wirenet->id2obj) == NULL) /* empty */ csch_op_remove(sheet, &wirenet->hdr); } /* figure if wirenet is a single segment and matches line's segment; keep the original wirenet with the original line and create new wirenet for each different segment */ static void csch_wirenet_newseg2wirenets(csch_sheet_t *sheet, crmap_t *map, csch_line_t *line, vtp0_t *new_wirenets) { int my_seg; htpi_entry_t *e; csch_cgrp_t **wn, *wn_; my_seg = htpi_get(&map->obj2seg, line); /* rnd_trace("my_seg=%d\n", my_seg);*/ for(e = htpi_first(&map->obj2seg); e != NULL; e = htpi_next(&map->obj2seg, e)) { csch_chdr_t *obj = e->key; int seg = e->value; /* rnd_trace(" seg: %d\n", seg);*/ if (!csch_obj_is_junction(&line->hdr)) { /* real wire lines should not get removed */ assert(!csch_obj_is_deleted(&line->hdr)); } if ((seg != my_seg) && (seg >= 0)) { wn = (csch_cgrp_t **)vtp0_get(new_wirenets, seg, 0); if ((wn == NULL) || (*wn == NULL)) { wn_ = csch_wirenet_new_from(sheet, line->hdr.parent); if (line->hdr.parent != NULL) wn_->hdr.selected = line->hdr.parent->hdr.selected; vtp0_set(new_wirenets, seg, wn_); wn = &wn_; } (*wn)->wirenet_split_lock = 1; if (obj->parent != 0) obj->parent->wirenet_split_lock = 1; csch_op_move_into(sheet, *wn, obj, 0, 0); if (obj->parent != 0) obj->parent->wirenet_split_lock = 0; (*wn)->wirenet_split_lock = 0; /* rnd_trace(" moved %d to wn %d\n", obj->oid, (*wn)->hdr.oid);*/ } if (!csch_obj_is_junction(&line->hdr)) { /* real wire lines should not get removed */ assert(!csch_obj_is_deleted(&line->hdr)); } } } void csch_wirenet_recalc(csch_sheet_t *sheet, csch_cgrp_t *line_wn) { crmap_t map; csch_line_t *line; htip_entry_t *e; vtp0_t new_wirenets = {0}; long n; map_wirenet_crossings(&map, sheet, line_wn, 1, 0, 1); /* pick up floaters */ map_misc_to_closest(&map); /* collect new wirenets; pick one line randomly for the segment that is kept in the old/existing wirenet */ e = htip_first(&line_wn->id2obj); if (e == NULL) return; line = e->value; csch_wirenet_newseg2wirenets(sheet, &map, line, &new_wirenets); for(n = 0; n < new_wirenets.used; n++) { if ((new_wirenets.array[n] != NULL) && (!csch_obj_is_deleted(new_wirenets.array[n]))) { /* in case it now touches another wirenet, merge them */ csch_wirenet_recalc_merges(sheet, new_wirenets.array[n]); /* recalc junctions and conns if not merged */ if (!csch_obj_is_deleted(new_wirenets.array[n])) { wirenet_remove_or_recalc(sheet, new_wirenets.array[n]); csch_wirenet_recalc_wirenet_conn(sheet, new_wirenets.array[n]); } } } if (!csch_obj_is_deleted(&line_wn->hdr)) wirenet_remove_or_recalc(sheet, line_wn); map_uninit(&map); vtp0_uninit(&new_wirenets); } void csch_wirenet_recalc_line_chg(csch_sheet_t *sheet, csch_line_t *line) { crmap_t map; vtp0_t new_wirenets = {0}; csch_cgrp_t *line_wn = line->hdr.parent; long n; assert(!csch_obj_is_deleted(&line->hdr)); if ((line_wn == NULL) || (line_wn->role != CSCH_ROLE_WIRE_NET)) return; if ((line->spec.p1.x == line->spec.p2.x) && (line->spec.p1.y == line->spec.p2.y)) { /* avoid a whole lot of corner cases by simply removing a wire line the user resized to 0 length */ /* rnd_trace("zero length line removed\n");*/ csch_op_remove(sheet, line); csch_wirenet_recalc_junctions(sheet, line_wn); return; } if (sheet->util_wirenet.recalc_inhibit) { htpi_set(&sheet->util_wirenet.recalc_wn, line_wn, 1); return; } map_wirenet_crossings(&map, sheet, line_wn, 1, 0, 1); /* pick up floaters */ map_misc_to_closest(&map); csch_wirenet_newseg2wirenets(sheet, &map, line, &new_wirenets); /* Install conns at new coords before net merge; order matters, because if the wirenet of the edited line gets merged into another, existing wirenet, that will inherit the connections we find here; but if connections are calculated only after the merge in csch_wirenet_newline_merge_parent(), then "line" is already a deleted object from the old, now deleted wirenet and the connection is not made on deleted objects. Test case: tests/manual/cn1 */ csch_wirenet_recalc_obj_conn(sheet, &line->hdr); /* check if the endpoints of the line now connects other wirenets and merge them */ { csch_cgrp_t *parent; int merge_res; merge_res = csch_wirenet_newline_merge_parent(sheet, line->inst.c.p1.x, line->inst.c.p1.y, line->inst.c.p2.x, line->inst.c.p2.y, &parent, MERGE_WARN_NON_FATAL, &line->hdr); if (merge_res > 0) csch_wirenet_recalc_junctions(sheet, parent); } for(n = 0; n < new_wirenets.used; n++) { if ((new_wirenets.array[n] != NULL) && (!csch_obj_is_deleted(new_wirenets.array[n]))) { wirenet_remove_or_recalc(sheet, new_wirenets.array[n]); csch_wirenet_recalc_wirenet_conn(sheet, new_wirenets.array[n]); } } if (!csch_obj_is_deleted(&line_wn->hdr)) wirenet_remove_or_recalc(sheet, line_wn); map_uninit(&map); } void csch_wirenet_recalc_freeze(csch_sheet_t *sheet) { int last = sheet->util_wirenet.recalc_inhibit; sheet->util_wirenet.recalc_inhibit++; if (last > sheet->util_wirenet.recalc_inhibit) rnd_message(RND_MSG_ERROR, "sheet->util_wirenet.recalc_inhibit overflow; save and exit!\n"); } void csch_wirenet_recalc_unfreeze(csch_sheet_t *sheet) { if (sheet->util_wirenet.recalc_inhibit == 0) { rnd_message(RND_MSG_ERROR, "sheet->util_wirenet.recalc_inhibit underflow; save and exit!\n"); return; } sheet->util_wirenet.recalc_inhibit--; if (sheet->util_wirenet.recalc_inhibit == 0) { htpi_entry_t *e; for(e = htpi_first(&sheet->util_wirenet.recalc_wn); e != NULL; e = htpi_next(&sheet->util_wirenet.recalc_wn, e)) { csch_cgrp_t *grp = e->key; if (!csch_obj_is_deleted(&grp->hdr)) csch_wirenet_recalc(sheet, grp); } for(e = htpi_first(&sheet->util_wirenet.recalc_wn); e != NULL; e = htpi_first(&sheet->util_wirenet.recalc_wn)) { csch_cgrp_t *grp = e->key; csch_wirenet_recalc_merges(sheet, grp); csch_wirenet_recalc_junctions(sheet, grp); htpi_delentry(&sheet->util_wirenet.recalc_wn, e); } } } int csch_wire_count_junctions(csch_chdr_t *wno, int *mid_cnt_out) { csch_cgrp_t *wn = wno->parent; csch_line_t *wline = (csch_line_t *)wno; htip_entry_t *e; int cnt = 0, mid_cnt = 0; assert(wn->role == CSCH_ROLE_WIRE_NET); assert(wno->type == CSCH_CTYPE_LINE); for(e = htip_first(&wn->id2obj); e != NULL; e = htip_next(&wn->id2obj, e)) { csch_chdr_t *junc = e->value; g2d_cvect_t jv; double offs; if (!csch_obj_is_junction(junc)) continue; jv.x = (double)(junc->bbox.x1 + junc->bbox.x2)/2.0; jv.y = (double)(junc->bbox.y1 + junc->bbox.y2)/2.0; offs = g2d__offs_cline_pt(&wline->inst.c, jv); if ((offs > 0.0) && (offs < 1.0)) mid_cnt++; cnt++; } if (mid_cnt_out != NULL) *mid_cnt_out = mid_cnt; return cnt; } typedef struct { csch_chdr_t *res; g2d_cline_t path; } safe_wire_t; static csch_rtree_dir_t safe_wire_cb(void *ctx_, void *obj_, const csch_rtree_box_t *box) { safe_wire_t *ctx = (safe_wire_t *)ctx_; csch_line_t *line = obj_; /* accept lines that are in a wirenet */ if ((line->hdr.type == CSCH_CTYPE_LINE) && (line->hdr.parent != NULL) && (line->hdr.parent->role == CSCH_ROLE_WIRE_NET)) { g2d_vect_t ip[2]; g2d_offs_t offs[2]; int n, len; /* check if any intersection is on the line's endpoint */ len = g2d_iscp_cline_cline(&line->inst.c, &ctx->path, ip, offs); for(n = 0; n < len; n++) { if ((offs[n] == 0.0) || (offs[n] == 1.0)) { if ((ip[n].x == ctx->path.p1.x) && (ip[n].y == ctx->path.p1.y)) continue; /* hitting endpoint on path is okay */ if ((ip[n].x == ctx->path.p2.x) && (ip[n].y == ctx->path.p2.y)) continue; ctx->res = obj_; return csch_RTREE_DIR_FOUND_STOP; } } } return csch_RTREE_DIR_NOT_FOUND_CONT; } int csch_is_wireline_safe(csch_sheet_t *sheet, csch_coord_t x1, csch_coord_t y1, csch_coord_t x2, csch_coord_t y2) { csch_rtree_dir_t res; safe_wire_t ctx = {0}; csch_rtree_box_t query; ctx.path.p1.x = x1; ctx.path.p1.y = y1; ctx.path.p2.x = x2; ctx.path.p2.y = y2; if (x1 > x2) rnd_swap(csch_coord_t, x1, x2); if (y1 > y2) rnd_swap(csch_coord_t, y1, y2); query.x1 = x1-2; query.y1 = y1-2; query.x2 = x2+2; query.y2 = y2+2; res = csch_rtree_search_obj(&sheet->dsply[CSCH_DSPLY_WIRE], &query, safe_wire_cb, &ctx); return !(res & csch_RTREE_DIR_FOUND); } void csch_wirenet_post_remove_checks(csch_sheet_t *sheet, csch_cgrp_t *wn, int undoable) { htip_entry_t *e, *next; int has_wires = 0; /* check if the wirenet has anything else than floaters and connections */ for(e = htip_first(&wn->id2obj); e != NULL; e = htip_next(&wn->id2obj, e)) { csch_chdr_t *obj = e->value; if (!obj->floater && (obj->type != CSCH_CTYPE_CONN) && !csch_obj_is_junction(obj)) { has_wires = 1; break; } } if (!has_wires) { /* remove all floaters */ for(e = htip_first(&wn->id2obj); e != NULL; e = next) { csch_chdr_t *obj = e->value; next = htip_next(&wn->id2obj, e); if (obj->floater) { if (undoable) csch_op_remove(sheet, obj); else csch_cnc_remove(sheet, obj); } } } }