src/find.c

   1 /*
   2  *
   3  *                            COPYRIGHT
   4  *
   5  *  PCB, interactive printed circuit board design
   6  *  Copyright (C) 1994,1995,1996, 2005 Thomas Nau
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21  *
  22  *  Contact addresses for paper mail and Email:
  23  *  Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
  24  *  Thomas.Nau@rz.uni-ulm.de
  25  *
  26  */
  27
  28
  29 /*
  30  * short description:
  31  * - lists for pins and vias, lines, arcs, pads and for polygons are created.
  32  *   Every object that has to be checked is added to its list.
  33  *   Coarse searching is accomplished with the data rtrees.
  34  * - there's no 'speed-up' mechanism for polygons because they are not used
  35  *   as often as other objects
  36  * - the maximum distance between line and pin ... would depend on the angle
  37  *   between them. To speed up computation the limit is set to one half
  38  *   of the thickness of the objects (cause of square pins).
  39  *
  40  * PV:  means pin or via (objects that connect layers)
  41  * LO:  all non PV objects (layer objects like lines, arcs, polygons, pads)
  42  *
  43  * 1. first, the LO or PV at the given coordinates is looked up
  44  * 2. all LO connections to that PV are looked up next
  45  * 3. lookup of all LOs connected to LOs from (2).
  46  *    This step is repeated until no more new connections are found.
  47  * 4. lookup all PVs connected to the LOs from (2) and (3)
  48  * 5. start again with (1) for all new PVs from (4)
  49  *
  50  * Intersection of line <--> circle:
  51  * - calculate the signed distance from the line to the center,
  52  *   return false if abs(distance) > R
  53  * - get the distance from the line <--> distancevector intersection to
  54  *   (X1,Y1) in range [0,1], return true if 0 <= distance <= 1
  55  * - depending on (r > 1.0 or r < 0.0) check the distance of X2,Y2 or X1,Y1
  56  *   to X,Y
  57  *
  58  * Intersection of line <--> line:
  59  * - see the description of 'LineLineIntersect()'
  60  */
  61
  62 /* routines to find connections between pins, vias, lines...
  63  */
  64 #ifdef HAVE_CONFIG_H
  65 #include "config.h"
  66 #endif
  67
  68 #include <setjmp.h>
  69 #include <assert.h>
  70
  71 #include "global.h"
  72
  73 #include "data.h"
  74 #include "draw.h"
  75 #include "error.h"
  76 #include "find.h"
  77 #include "misc.h"
  78 #include "rtree.h"
  79 #include "polygon.h"
  80 #include "pcb-printf.h"
  81 #include "search.h"
  82 #include "set.h"
  83 #include "undo.h"
  84 #include "rats.h"
  85
  86 #ifdef HAVE_LIBDMALLOC
  87 #include <dmalloc.h>
  88 #endif
  89
  90 #undef DEBUG
  91
  92 /* ---------------------------------------------------------------------------
  93  * some local macros
  94  */
  95
  96 #define SEPARATE(FP)                                                    \
  97         {                                                                                       \
  98                 int     i;                                                                      \
  99                 fputc('#', (FP));                                               \
 100                 for (i = Settings.CharPerLine; i; i--)  \
 101                         fputc('=', (FP));                                       \
 102                 fputc('\n', (FP));                                              \
 103         }
 104
 105 #define LIST_ENTRY(list,I)      (((AnyObjectType **)list->Data)[(I)])
 106 #define PADLIST_ENTRY(L,I)      (((PadType **)PadList[(L)].Data)[(I)])
 107 #define LINELIST_ENTRY(L,I)     (((LineType **)LineList[(L)].Data)[(I)])
 108 #define ARCLIST_ENTRY(L,I)      (((ArcType **)ArcList[(L)].Data)[(I)])
 109 #define RATLIST_ENTRY(I)        (((RatType **)RatList.Data)[(I)])
 110 #define POLYGONLIST_ENTRY(L,I)  (((PolygonType **)PolygonList[(L)].Data)[(I)])
 111 #define PVLIST_ENTRY(I)         (((PinType **)PVList.Data)[(I)])
 112
 113 #define IS_PV_ON_RAT(PV, Rat) \
 114         (IsPointOnLineEnd((PV)->X,(PV)->Y, (Rat)))
 115
 116 #define IS_PV_ON_ARC(PV, Arc)   \
 117         (TEST_FLAG(SQUAREFLAG, (PV)) ? \
 118                 IsArcInRectangle( \
 119                         (PV)->X -MAX(((PV)->Thickness+1)/2 +Bloat,0), (PV)->Y -MAX(((PV)->Thickness+1)/2 +Bloat,0), \
 120                         (PV)->X +MAX(((PV)->Thickness+1)/2 +Bloat,0), (PV)->Y +MAX(((PV)->Thickness+1)/2 +Bloat,0), \
 121                         (Arc)) : \
 122                 IsPointOnArc((PV)->X,(PV)->Y,MAX((PV)->Thickness/2.0 + Bloat,0.0), (Arc)))
 123
 124 #define IS_PV_ON_PAD(PV,Pad) \
 125         ( IsPointInPad((PV)->X, (PV)->Y, MAX((PV)->Thickness/2 +Bloat,0), (Pad)))
 126
 127 #define BOTTOM_LAYER 0
 128 #define TOP_LAYER 1
 129
 130 static DrcViolationType
 131 *pcb_drc_violation_new (const char *title,
 132                         const char *explanation,
 133                         Coord x, Coord y,
 134                         Angle angle,
 135                         bool have_measured,
 136                         Coord measured_value,
 137                         Coord required_value,
 138                         int object_count,
 139                         long int *object_id_list,
 140                         int *object_type_list)
 141 {
 142   DrcViolationType *violation = (DrcViolationType *)malloc (sizeof (DrcViolationType));
 143
 144   violation->title = strdup (title);
 145   violation->explanation = strdup (explanation);
 146   violation->x = x;
 147   violation->y = y;
 148   violation->angle = angle;
 149   violation->have_measured = have_measured;
 150   violation->measured_value = measured_value;
 151   violation->required_value = required_value;
 152   violation->object_count = object_count;
 153   violation->object_id_list = object_id_list;
 154   violation->object_type_list = object_type_list;
 155
 156   return violation;
 157 }
 158
 159 static void
 160 pcb_drc_violation_free (DrcViolationType *violation)
 161 {
 162   free (violation->title);
 163   free (violation->explanation);
 164   free (violation);
 165 }
 166
 167 static GString *drc_dialog_message;
 168 static void
 169 reset_drc_dialog_message(void)
 170 {
 171   if (drc_dialog_message)
 172     g_string_free (drc_dialog_message, FALSE);
 173   drc_dialog_message = g_string_new ("");
 174   if (gui->drc_gui != NULL)
 175     {
 176       gui->drc_gui->reset_drc_dialog_message ();
 177     }
 178 }
 179 static void
 180 append_drc_dialog_message(const char *fmt, ...)
 181 {
 182   gchar *new_str;
 183   va_list ap;
 184   va_start (ap, fmt);
 185   new_str = pcb_vprintf (fmt, ap);
 186   g_string_append (drc_dialog_message, new_str);
 187   va_end (ap);
 188   g_free (new_str);
 189 }
 190
 191 static void GotoError (void);
 192
 193 static void
 194 append_drc_violation (DrcViolationType *violation)
 195 {
 196   if (gui->drc_gui != NULL)
 197     {
 198       gui->drc_gui->append_drc_violation (violation);
 199     }
 200   else
 201     {
 202       /* Fallback to formatting the violation message as text */
 203       append_drc_dialog_message ("%s\n", violation->title);
 204       append_drc_dialog_message (_("%m+near %$mD\n"),
 205                                  Settings.grid_unit->allow,
 206                                  violation->x, violation->y);
 207       GotoError ();
 208     }
 209
 210   if (gui->drc_gui == NULL || gui->drc_gui->log_drc_violations )
 211     {
 212       Message (_("WARNING!  Design Rule error - %s\n"), violation->title);
 213       Message (_("%m+near location %$mD\n"),
 214                Settings.grid_unit->allow,
 215                violation->x, violation->y);
 216     }
 217 }
 218 /*
 219  * message when asked about continuing DRC checks after next
 220  * violation is found.
 221  */
 222 #define DRC_CONTINUE _("Press Next to continue DRC checking")
 223 #define DRC_NEXT _("Next")
 224 #define DRC_CANCEL _("Cancel")
 225
 226 static int
 227 throw_drc_dialog(void)
 228 {
 229   int r;
 230
 231   if (gui->drc_gui != NULL)
 232     {
 233       r = gui->drc_gui->throw_drc_dialog ();
 234     }
 235   else
 236     {
 237       /* Fallback to formatting the violation message as text */
 238       append_drc_dialog_message (DRC_CONTINUE);
 239       r = gui->confirm_dialog (drc_dialog_message->str, DRC_CANCEL, DRC_NEXT);
 240       reset_drc_dialog_message();
 241     }
 242   return r;
 243 }
 244
 245 /* ---------------------------------------------------------------------------
 246  * some local types
 247  *
 248  * the two 'dummy' structs for PVs and Pads are necessary for creating
 249  * connection lists which include the element's name
 250  */
 251 typedef struct
 252 {
 253   void **Data;                  /* pointer to index data */
 254   Cardinal Location,            /* currently used position */
 255     DrawLocation, Number,       /* number of objects in list */
 256     Size;
 257 } ListType;
 258
 259 /* ---------------------------------------------------------------------------
 260  * some local identifiers
 261  */
 262 static Coord Bloat = 0;
 263 static void *thing_ptr1, *thing_ptr2, *thing_ptr3;
 264 static int thing_type;
 265 static bool User = false;    /* user action causing this */
 266 static bool drc = false;     /* whether to stop if finding something not found */
 267 static Cardinal drcerr_count;   /* count of drc errors */
 268 static Cardinal TotalP, TotalV;
 269 static ListType LineList[MAX_LAYER],    /* list of objects to */
 270   PolygonList[MAX_LAYER], ArcList[MAX_LAYER], PadList[2], RatList, PVList;
 271
 272 /* ---------------------------------------------------------------------------
 273  * some local prototypes
 274  */
 275 static bool LookupLOConnectionsToLine (LineType *, Cardinal, int, bool, bool);
 276 static bool LookupLOConnectionsToPad (PadType *, Cardinal, int, bool);
 277 static bool LookupLOConnectionsToPolygon (PolygonType *, Cardinal, int, bool);
 278 static bool LookupLOConnectionsToArc (ArcType *, Cardinal, int, bool);
 279 static bool LookupLOConnectionsToRatEnd (PointType *, Cardinal, int);
 280 static bool IsRatPointOnLineEnd (PointType *, LineType *);
 281 static bool ArcArcIntersect (ArcType *, ArcType *);
 282 static bool PrepareNextLoop (FILE *);
 283 static void DrawNewConnections (void);
 284 static void DumpList (void);
 285 static void LocateError (Coord *, Coord *);
 286 static void BuildObjectList (int *, long int **, int **);
 287 static bool SetThing (int, void *, void *, void *);
 288 static bool IsArcInPolygon (ArcType *, PolygonType *);
 289 static bool IsLineInPolygon (LineType *, PolygonType *);
 290 static bool IsPadInPolygon (PadType *, PolygonType *);
 291 static bool IsPolygonInPolygon (PolygonType *, PolygonType *);
 292
 293 /* ---------------------------------------------------------------------------
 294  * some of the 'pad' routines are the same as for lines because the 'pad'
 295  * struct starts with a line struct. See global.h for details
 296  */
 297 bool
 298 LinePadIntersect (LineType *Line, PadType *Pad)
 299 {
 300   return LineLineIntersect ((Line), (LineType *)Pad);
 301 }
 302
 303 bool
 304 ArcPadIntersect (ArcType *Arc, PadType *Pad)
 305 {
 306   return LineArcIntersect ((LineType *) (Pad), (Arc));
 307 }
 308
 309 static bool
 310 add_object_to_list (ListType *list, int type, void *ptr1, void *ptr2, void *ptr3, int flag)
 311 {
 312   AnyObjectType *object = (AnyObjectType *)ptr2;
 313
 314   if (User)
 315     AddObjectToFlagUndoList (type, ptr1, ptr2, ptr3);
 316
 317   SET_FLAG (flag, object);
 318   LIST_ENTRY (list, list->Number) = object;
 319   list->Number++;
 320
 321 #ifdef DEBUG
 322   if (list.Number > list.Size)
 323     printf ("add_object_to_list overflow! type=%i num=%d size=%d\n", type, list.Number, list.Size);
 324 #endif
 325
 326   if (drc && !TEST_FLAG (SELECTEDFLAG, object))
 327     return (SetThing (type, ptr1, ptr2, ptr3));
 328   return false;
 329 }
 330
 331 static bool
 332 ADD_PV_TO_LIST (PinType *Pin, int flag)
 333 {
 334   return add_object_to_list (&PVList, Pin->Element ? PIN_TYPE : VIA_TYPE,
 335                              Pin->Element ? Pin->Element : Pin, Pin, Pin, flag);
 336 }
 337
 338 static bool
 339 ADD_PAD_TO_LIST (Cardinal L, PadType *Pad, int flag)
 340 {
 341   return add_object_to_list (&PadList[L], PAD_TYPE, Pad->Element, Pad, Pad, flag);
 342 }
 343
 344 static bool
 345 ADD_LINE_TO_LIST (Cardinal L, LineType *Ptr, int flag)
 346 {
 347   return add_object_to_list (&LineList[L], LINE_TYPE, LAYER_PTR (L), Ptr, Ptr, flag);
 348 }
 349
 350 static bool
 351 ADD_ARC_TO_LIST (Cardinal L, ArcType *Ptr, int flag)
 352 {
 353   return add_object_to_list (&ArcList[L], ARC_TYPE, LAYER_PTR (L), Ptr, Ptr, flag);
 354 }
 355
 356 static bool
 357 ADD_RAT_TO_LIST (RatType *Ptr, int flag)
 358 {
 359   return add_object_to_list (&RatList, RATLINE_TYPE, Ptr, Ptr, Ptr, flag);
 360 }
 361
 362 static bool
 363 ADD_POLYGON_TO_LIST (Cardinal L, PolygonType *Ptr, int flag)
 364 {
 365   return add_object_to_list (&PolygonList[L], POLYGON_TYPE, LAYER_PTR (L), Ptr, Ptr, flag);
 366 }
 367
 368 static BoxType
 369 expand_bounds (BoxType *box_in)
 370 {
 371   BoxType box_out = *box_in;
 372
 373   if (Bloat > 0)
 374     {
 375       box_out.X1 -= Bloat;
 376       box_out.X2 += Bloat;
 377       box_out.Y1 -= Bloat;
 378       box_out.Y2 += Bloat;
 379     }
 380
 381   return box_out;
 382 }
 383
 384 bool
 385 PinLineIntersect (PinType *PV, LineType *Line)
 386 {
 387   /* IsLineInRectangle already has Bloat factor */
 388   return TEST_FLAG (SQUAREFLAG,
 389                     PV) ? IsLineInRectangle (PV->X - (PIN_SIZE (PV) + 1) / 2,
 390                                              PV->Y - (PIN_SIZE (PV) + 1) / 2,
 391                                              PV->X + (PIN_SIZE (PV) + 1) / 2,
 392                                              PV->Y + (PIN_SIZE (PV) + 1) / 2,
 393                                              Line) : IsPointInPad (PV->X,
 394                                                                     PV->Y,
 395                                                                    MAX (PIN_SIZE (PV)
 396                                                                          /
 397                                                                          2.0 +
 398                                                                          Bloat,
 399                                                                          0.0),
 400                                                                     (PadType *)Line);
 401 }
 402
 403
 404 bool
 405 SetThing (int type, void *ptr1, void *ptr2, void *ptr3)
 406 {
 407   thing_ptr1 = ptr1;
 408   thing_ptr2 = ptr2;
 409   thing_ptr3 = ptr3;
 410   thing_type = type;
 411   return true;
 412 }
 413
 414 bool
 415 BoxBoxIntersection (BoxType *b1, BoxType *b2)
 416 {
 417   if (b2->X2 < b1->X1 || b2->X1 > b1->X2)
 418     return false;
 419   if (b2->Y2 < b1->Y1 || b2->Y1 > b1->Y2)
 420     return false;
 421   return true;
 422 }
 423
 424 static bool
 425 PadPadIntersect (PadType *p1, PadType *p2)
 426 {
 427   return LinePadIntersect ((LineType *) p1, p2);
 428 }
 429
 430 static inline bool
 431 PV_TOUCH_PV (PinType *PV1, PinType *PV2)
 432 {
 433   double t1, t2;
 434   BoxType b1, b2;
 435
 436   t1 = MAX (PV1->Thickness / 2.0 + Bloat, 0);
 437   t2 = MAX (PV2->Thickness / 2.0 + Bloat, 0);
 438   if (IsPointOnPin (PV1->X, PV1->Y, t1, PV2)
 439       || IsPointOnPin (PV2->X, PV2->Y, t2, PV1))
 440     return true;
 441   if (!TEST_FLAG (SQUAREFLAG, PV1) || !TEST_FLAG (SQUAREFLAG, PV2))
 442     return false;
 443   /* check for square/square overlap */
 444   b1.X1 = PV1->X - t1;
 445   b1.X2 = PV1->X + t1;
 446   b1.Y1 = PV1->Y - t1;
 447   b1.Y2 = PV1->Y + t1;
 448   t2 = PV2->Thickness / 2.0;
 449   b2.X1 = PV2->X - t2;
 450   b2.X2 = PV2->X + t2;
 451   b2.Y1 = PV2->Y - t2;
 452   b2.Y2 = PV2->Y + t2;
 453   return BoxBoxIntersection (&b1, &b2);
 454 }
 455
 456 /* ---------------------------------------------------------------------------
 457  * releases all allocated memory
 458  */
 459 static void
 460 FreeLayoutLookupMemory (void)
 461 {
 462   Cardinal i;
 463
 464   for (i = 0; i < max_copper_layer; i++)
 465     {
 466       free (LineList[i].Data);
 467       LineList[i].Data = NULL;
 468       free (ArcList[i].Data);
 469       ArcList[i].Data = NULL;
 470       free (PolygonList[i].Data);
 471       PolygonList[i].Data = NULL;
 472     }
 473   free (PVList.Data);
 474   PVList.Data = NULL;
 475   free (RatList.Data);
 476   RatList.Data = NULL;
 477 }
 478
 479 static void
 480 FreeComponentLookupMemory (void)
 481 {
 482   free (PadList[0].Data);
 483   PadList[0].Data = NULL;
 484   free (PadList[1].Data);
 485   PadList[1].Data = NULL;
 486 }
 487
 488 /* ---------------------------------------------------------------------------
 489  * allocates memory for component related stacks ...
 490  * initializes index and sorts it by X1 and X2
 491  */
 492 static void
 493 InitComponentLookup (void)
 494 {
 495   Cardinal NumberOfPads[2];
 496   Cardinal i;
 497
 498   /* initialize pad data; start by counting the total number
 499    * on each of the two possible layers
 500    */
 501   NumberOfPads[TOP_SIDE] = NumberOfPads[BOTTOM_SIDE] = 0;
 502   ALLPAD_LOOP (PCB->Data);
 503   {
 504     if (TEST_FLAG (ONSOLDERFLAG, pad))
 505       NumberOfPads[BOTTOM_SIDE]++;
 506     else
 507       NumberOfPads[TOP_SIDE]++;
 508   }
 509   ENDALL_LOOP;
 510   for (i = 0; i < 2; i++)
 511     {
 512       /* allocate memory for working list */
 513       PadList[i].Data = (void **)calloc (NumberOfPads[i], sizeof (PadType *));
 514
 515       /* clear some struct members */
 516       PadList[i].Location = 0;
 517       PadList[i].DrawLocation = 0;
 518       PadList[i].Number = 0;
 519       PadList[i].Size = NumberOfPads[i];
 520     }
 521 }
 522
 523 /* ---------------------------------------------------------------------------
 524  * allocates memory for component related stacks ...
 525  * initializes index and sorts it by X1 and X2
 526  */
 527 static void
 528 InitLayoutLookup (void)
 529 {
 530   Cardinal i;
 531
 532   /* initialize line arc and polygon data */
 533   for (i = 0; i < max_copper_layer; i++)
 534     {
 535       LayerType *layer = LAYER_PTR (i);
 536
 537       if (layer->LineN)
 538         {
 539           /* allocate memory for line pointer lists */
 540           LineList[i].Data = (void **)calloc (layer->LineN, sizeof (LineType *));
 541           LineList[i].Size = layer->LineN;
 542         }
 543       if (layer->ArcN)
 544         {
 545           ArcList[i].Data = (void **)calloc (layer->ArcN, sizeof (ArcType *));
 546           ArcList[i].Size = layer->ArcN;
 547         }
 548
 549
 550       /* allocate memory for polygon list */
 551       if (layer->PolygonN)
 552         {
 553           PolygonList[i].Data = (void **)calloc (layer->PolygonN, sizeof (PolygonType *));
 554           PolygonList[i].Size = layer->PolygonN;
 555         }
 556
 557       /* clear some struct members */
 558       LineList[i].Location = 0;
 559       LineList[i].DrawLocation = 0;
 560       LineList[i].Number = 0;
 561       ArcList[i].Location = 0;
 562       ArcList[i].DrawLocation = 0;
 563       ArcList[i].Number = 0;
 564       PolygonList[i].Location = 0;
 565       PolygonList[i].DrawLocation = 0;
 566       PolygonList[i].Number = 0;
 567     }
 568
 569   if (PCB->Data->pin_tree)
 570     TotalP = PCB->Data->pin_tree->size;
 571   else
 572     TotalP = 0;
 573   if (PCB->Data->via_tree)
 574     TotalV = PCB->Data->via_tree->size;
 575   else
 576     TotalV = 0;
 577   /* allocate memory for 'new PV to check' list and clear struct */
 578   PVList.Data = (void **)calloc (TotalP + TotalV, sizeof (PinType *));
 579   PVList.Size = TotalP + TotalV;
 580   PVList.Location = 0;
 581   PVList.DrawLocation = 0;
 582   PVList.Number = 0;
 583   /* Initialize ratline data */
 584   RatList.Data = (void **)calloc (PCB->Data->RatN, sizeof (RatType *));
 585   RatList.Size = PCB->Data->RatN;
 586   RatList.Location = 0;
 587   RatList.DrawLocation = 0;
 588   RatList.Number = 0;
 589 }
 590
 591 struct pv_info
 592 {
 593   Cardinal layer;
 594   PinType *pv;
 595   int flag;
 596   jmp_buf env;
 597 };
 598
 599 static int
 600 LOCtoPVline_callback (const BoxType * b, void *cl)
 601 {
 602   LineType *line = (LineType *) b;
 603   struct pv_info *i = (struct pv_info *) cl;
 604
 605   if (!TEST_FLAG (i->flag, line) && PinLineIntersect (i->pv, line) &&
 606       !TEST_FLAG (HOLEFLAG, i->pv))
 607     {
 608       if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
 609         longjmp (i->env, 1);
 610     }
 611   return 0;
 612 }
 613
 614 static int
 615 LOCtoPVarc_callback (const BoxType * b, void *cl)
 616 {
 617   ArcType *arc = (ArcType *) b;
 618   struct pv_info *i = (struct pv_info *) cl;
 619
 620   if (!TEST_FLAG (i->flag, arc) && IS_PV_ON_ARC (i->pv, arc) &&
 621       !TEST_FLAG (HOLEFLAG, i->pv))
 622     {
 623       if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
 624         longjmp (i->env, 1);
 625     }
 626   return 0;
 627 }
 628
 629 static int
 630 LOCtoPVpad_callback (const BoxType * b, void *cl)
 631 {
 632   PadType *pad = (PadType *) b;
 633   struct pv_info *i = (struct pv_info *) cl;
 634
 635   if (!TEST_FLAG (i->flag, pad) && IS_PV_ON_PAD (i->pv, pad) &&
 636       !TEST_FLAG (HOLEFLAG, i->pv) &&
 637       ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE :
 638                        TOP_SIDE, pad, i->flag))
 639     longjmp (i->env, 1);
 640   return 0;
 641 }
 642
 643 static int
 644 LOCtoPVrat_callback (const BoxType * b, void *cl)
 645 {
 646   RatType *rat = (RatType *) b;
 647   struct pv_info *i = (struct pv_info *) cl;
 648
 649   if (!TEST_FLAG (i->flag, rat) && IS_PV_ON_RAT (i->pv, rat) &&
 650       ADD_RAT_TO_LIST (rat, i->flag))
 651     longjmp (i->env, 1);
 652   return 0;
 653 }
 654 static int
 655 LOCtoPVpoly_callback (const BoxType * b, void *cl)
 656 {
 657   PolygonType *polygon = (PolygonType *) b;
 658   struct pv_info *i = (struct pv_info *) cl;
 659
 660   /* if the pin doesn't have a therm and polygon is clearing
 661    * then it can't touch due to clearance, so skip the expensive
 662    * test. If it does have a therm, you still need to test
 663    * because it might not be inside the polygon, or it could
 664    * be on an edge such that it doesn't actually touch.
 665    */
 666   if (!TEST_FLAG (i->flag, polygon) && !TEST_FLAG (HOLEFLAG, i->pv) &&
 667                                        (TEST_THERM (i->layer, i->pv) ||
 668                                         !TEST_FLAG (CLEARPOLYFLAG,
 669                                                     polygon)
 670                                         || !i->pv->Clearance))
 671     {
 672       double wide = MAX (0.5 * i->pv->Thickness + Bloat, 0);
 673       if (TEST_FLAG (SQUAREFLAG, i->pv))
 674         {
 675           Coord x1 = i->pv->X - (i->pv->Thickness + 1 + Bloat) / 2;
 676           Coord x2 = i->pv->X + (i->pv->Thickness + 1 + Bloat) / 2;
 677           Coord y1 = i->pv->Y - (i->pv->Thickness + 1 + Bloat) / 2;
 678           Coord y2 = i->pv->Y + (i->pv->Thickness + 1 + Bloat) / 2;
 679           if (IsRectangleInPolygon (x1, y1, x2, y2, polygon)
 680               && ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
 681             longjmp (i->env, 1);
 682         }
 683       else if (TEST_FLAG (OCTAGONFLAG, i->pv))
 684         {
 685           POLYAREA *oct = OctagonPoly (i->pv->X, i->pv->Y, i->pv->Thickness / 2);
 686           if (isects (oct, polygon, true)
 687               && ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
 688             longjmp (i->env, 1);
 689         }
 690       else if (IsPointInPolygon (i->pv->X, i->pv->Y, wide,
 691                                  polygon)
 692                && ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
 693         longjmp (i->env, 1);
 694     }
 695   return 0;
 696 }
 697
 698 /* ---------------------------------------------------------------------------
 699  * checks if a PV is connected to LOs, if it is, the LO is added to
 700  * the appropriate list and the 'used' flag is set
 701  */
 702 static bool
 703 LookupLOConnectionsToPVList (int flag, bool AndRats)
 704 {
 705   Cardinal layer_no;
 706   struct pv_info info;
 707
 708   info.flag = flag;
 709
 710   /* loop over all PVs currently on list */
 711   while (PVList.Location < PVList.Number)
 712     {
 713       BoxType search_box;
 714
 715       /* get pointer to data */
 716       info.pv = PVLIST_ENTRY (PVList.Location);
 717       search_box = expand_bounds (&info.pv->BoundingBox);
 718
 719       /* check pads */
 720       if (setjmp (info.env) == 0)
 721         r_search (PCB->Data->pad_tree, &search_box, NULL,
 722                   LOCtoPVpad_callback, &info);
 723       else
 724         return true;
 725
 726       /* now all lines, arcs and polygons of the several layers */
 727       for (layer_no = 0; layer_no < max_copper_layer; layer_no++)
 728         {
 729           LayerType *layer = LAYER_PTR (layer_no);
 730
 731           if (layer->no_drc)
 732              continue;
 733
 734           info.layer = layer_no;
 735
 736           /* add touching lines */
 737           if (setjmp (info.env) == 0)
 738             r_search (layer->line_tree, &search_box,
 739                       NULL, LOCtoPVline_callback, &info);
 740           else
 741             return true;
 742           /* add touching arcs */
 743           if (setjmp (info.env) == 0)
 744             r_search (layer->arc_tree, &search_box,
 745                       NULL, LOCtoPVarc_callback, &info);
 746           else
 747             return true;
 748           /* check all polygons */
 749           if (setjmp (info.env) == 0)
 750             r_search (layer->polygon_tree, &search_box,
 751                       NULL, LOCtoPVpoly_callback, &info);
 752           else
 753             return true;
 754         }
 755       /* Check for rat-lines that may intersect the PV */
 756       if (AndRats)
 757         {
 758           if (setjmp (info.env) == 0)
 759             r_search (PCB->Data->rat_tree, &search_box, NULL,
 760                       LOCtoPVrat_callback, &info);
 761           else
 762             return true;
 763         }
 764       PVList.Location++;
 765     }
 766   return false;
 767 }
 768
 769 /* ---------------------------------------------------------------------------
 770  * find all connections between LO at the current list position and new LOs
 771  */
 772 static bool
 773 LookupLOConnectionsToLOList (int flag, bool AndRats)
 774 {
 775   bool done;
 776   Cardinal i, group, layer, ratposition,
 777     lineposition[MAX_LAYER],
 778     polyposition[MAX_LAYER], arcposition[MAX_LAYER], padposition[2];
 779
 780   /* copy the current LO list positions; the original data is changed
 781    * by 'LookupPVConnectionsToLOList()' which has to check the same
 782    * list entries plus the new ones
 783    */
 784   for (i = 0; i < max_copper_layer; i++)
 785     {
 786       lineposition[i] = LineList[i].Location;
 787       polyposition[i] = PolygonList[i].Location;
 788       arcposition[i]  = ArcList[i].Location;
 789     }
 790   for (i = 0; i < 2; i++)
 791     padposition[i] = PadList[i].Location;
 792   ratposition = RatList.Location;
 793
 794   /* loop over all new LOs in the list; recurse until no
 795    * more new connections in the layergroup were found
 796    */
 797   do
 798     {
 799       Cardinal *position;
 800
 801       if (AndRats)
 802         {
 803           position = &ratposition;
 804           for (; *position < RatList.Number; (*position)++)
 805             {
 806               group = RATLIST_ENTRY (*position)->group1;
 807               if (LookupLOConnectionsToRatEnd
 808                   (&(RATLIST_ENTRY (*position)->Point1), group, flag))
 809                 return (true);
 810               group = RATLIST_ENTRY (*position)->group2;
 811               if (LookupLOConnectionsToRatEnd
 812                   (&(RATLIST_ENTRY (*position)->Point2), group, flag))
 813                 return (true);
 814             }
 815         }
 816       /* loop over all layergroups */
 817       for (group = 0; group < max_group; group++)
 818         {
 819           Cardinal entry;
 820
 821           for (entry = 0; entry < PCB->LayerGroups.Number[group]; entry++)
 822             {
 823               layer = PCB->LayerGroups.Entries[group][entry];
 824
 825               /* be aware that the layer number equal max_copper_layer
 826                * and max_copper_layer+1 have a special meaning for pads
 827                */
 828               if (layer < max_copper_layer)
 829                 {
 830                   /* try all new lines */
 831                   position = &lineposition[layer];
 832                   for (; *position < LineList[layer].Number; (*position)++)
 833                     if (LookupLOConnectionsToLine
 834                         (LINELIST_ENTRY (layer, *position), group, flag, true, AndRats))
 835                       return (true);
 836
 837                   /* try all new arcs */
 838                   position = &arcposition[layer];
 839                   for (; *position < ArcList[layer].Number; (*position)++)
 840                     if (LookupLOConnectionsToArc
 841                         (ARCLIST_ENTRY (layer, *position), group, flag, AndRats))
 842                       return (true);
 843
 844                   /* try all new polygons */
 845                   position = &polyposition[layer];
 846                   for (; *position < PolygonList[layer].Number; (*position)++)
 847                     if (LookupLOConnectionsToPolygon
 848                         (POLYGONLIST_ENTRY (layer, *position), group, flag, AndRats))
 849                       return (true);
 850                 }
 851               else
 852                 {
 853                   /* try all new pads */
 854                   layer -= max_copper_layer;
 855                   if (layer > 1)
 856                     {
 857                       Message (_("bad layer number %d max_copper_layer=%d in find.c\n"),
 858                                layer, max_copper_layer);
 859                       return false;
 860                     }
 861                   position = &padposition[layer];
 862                   for (; *position < PadList[layer].Number; (*position)++)
 863                     if (LookupLOConnectionsToPad
 864                         (PADLIST_ENTRY (layer, *position), group, flag, AndRats))
 865                       return (true);
 866                 }
 867             }
 868         }
 869
 870       /* check if all lists are done; Later for-loops
 871        * may have changed the prior lists
 872        */
 873       done = !AndRats || ratposition >= RatList.Number;
 874       done = done && padposition[0] >= PadList[0].Number &&
 875                      padposition[1] >= PadList[1].Number;
 876       for (layer = 0; layer < max_copper_layer; layer++)
 877         done = done &&
 878                lineposition[layer] >= LineList[layer].Number &&
 879                arcposition[layer]  >= ArcList[layer].Number &&
 880                polyposition[layer] >= PolygonList[layer].Number;
 881     }
 882   while (!done);
 883   return (false);
 884 }
 885
 886 static int
 887 pv_pv_callback (const BoxType * b, void *cl)
 888 {
 889   PinType *pin = (PinType *) b;
 890   struct pv_info *i = (struct pv_info *) cl;
 891
 892   if (!TEST_FLAG (i->flag, pin) && PV_TOUCH_PV (i->pv, pin))
 893     {
 894       if (TEST_FLAG (HOLEFLAG, pin) || TEST_FLAG (HOLEFLAG, i->pv))
 895         {
 896           SET_FLAG (WARNFLAG, pin);
 897           Settings.RatWarn = true;
 898           if (pin->Element)
 899             Message (_("WARNING: Hole too close to pin.\n"));
 900           else
 901             Message (_("WARNING: Hole too close to via.\n"));
 902         }
 903       else if (ADD_PV_TO_LIST (pin, i->flag))
 904         longjmp (i->env, 1);
 905     }
 906   return 0;
 907 }
 908
 909 /* ---------------------------------------------------------------------------
 910  * searches for new PVs that are connected to PVs on the list
 911  */
 912 static bool
 913 LookupPVConnectionsToPVList (int flag)
 914 {
 915   Cardinal save_place;
 916   struct pv_info info;
 917
 918   info.flag = flag;
 919
 920   /* loop over all PVs on list */
 921   save_place = PVList.Location;
 922   while (PVList.Location < PVList.Number)
 923     {
 924       BoxType search_box;
 925
 926       /* get pointer to data */
 927       info.pv = PVLIST_ENTRY (PVList.Location);
 928       search_box = expand_bounds ((BoxType *)info.pv);
 929
 930       if (setjmp (info.env) == 0)
 931         r_search (PCB->Data->via_tree, &search_box, NULL,
 932                   pv_pv_callback, &info);
 933       else
 934         return true;
 935       if (setjmp (info.env) == 0)
 936         r_search (PCB->Data->pin_tree, &search_box, NULL,
 937                   pv_pv_callback, &info);
 938       else
 939         return true;
 940       PVList.Location++;
 941     }
 942   PVList.Location = save_place;
 943   return (false);
 944 }
 945
 946 struct lo_info
 947 {
 948   Cardinal layer;
 949   LineType *line;
 950   PadType *pad;
 951   ArcType *arc;
 952   PolygonType *polygon;
 953   RatType *rat;
 954   int flag;
 955   jmp_buf env;
 956 };
 957
 958 static int
 959 pv_line_callback (const BoxType * b, void *cl)
 960 {
 961   PinType *pv = (PinType *) b;
 962   struct lo_info *i = (struct lo_info *) cl;
 963
 964   if (!TEST_FLAG (i->flag, pv) && PinLineIntersect (pv, i->line))
 965     {
 966       if (TEST_FLAG (HOLEFLAG, pv))
 967         {
 968           SET_FLAG (WARNFLAG, pv);
 969           Settings.RatWarn = true;
 970           Message (_("WARNING: Hole too close to line.\n"));
 971         }
 972       else if (ADD_PV_TO_LIST (pv, i->flag))
 973         longjmp (i->env, 1);
 974     }
 975   return 0;
 976 }
 977
 978 static int
 979 pv_pad_callback (const BoxType * b, void *cl)
 980 {
 981   PinType *pv = (PinType *) b;
 982   struct lo_info *i = (struct lo_info *) cl;
 983
 984   if (!TEST_FLAG (i->flag, pv) && IS_PV_ON_PAD (pv, i->pad))
 985     {
 986       if (TEST_FLAG (HOLEFLAG, pv))
 987         {
 988           SET_FLAG (WARNFLAG, pv);
 989           Settings.RatWarn = true;
 990           Message (_("WARNING: Hole too close to pad.\n"));
 991         }
 992       else if (ADD_PV_TO_LIST (pv, i->flag))
 993         longjmp (i->env, 1);
 994     }
 995   return 0;
 996 }
 997
 998 static int
 999 pv_arc_callback (const BoxType * b, void *cl)
1000 {
1001   PinType *pv = (PinType *) b;
1002   struct lo_info *i = (struct lo_info *) cl;
1003
1004   if (!TEST_FLAG (i->flag, pv) && IS_PV_ON_ARC (pv, i->arc))
1005     {
1006       if (TEST_FLAG (HOLEFLAG, pv))
1007         {
1008           SET_FLAG (WARNFLAG, pv);
1009           Settings.RatWarn = true;
1010           Message (_("WARNING: Hole touches arc.\n"));
1011         }
1012       else if (ADD_PV_TO_LIST (pv, i->flag))
1013         longjmp (i->env, 1);
1014     }
1015   return 0;
1016 }
1017
1018 static int
1019 pv_poly_callback (const BoxType * b, void *cl)
1020 {
1021   PinType *pv = (PinType *) b;
1022   struct lo_info *i = (struct lo_info *) cl;
1023
1024   /* note that holes in polygons are ok, so they don't generate warnings. */
1025   if (!TEST_FLAG (i->flag, pv) && !TEST_FLAG (HOLEFLAG, pv) &&
1026                                   (TEST_THERM (i->layer, pv) ||
1027                                    !TEST_FLAG (CLEARPOLYFLAG, i->polygon) ||
1028                                    !pv->Clearance))
1029     {
1030       if (TEST_FLAG (SQUAREFLAG, pv))
1031         {
1032           Coord x1, x2, y1, y2;
1033           x1 = pv->X - (PIN_SIZE (pv) + 1 + Bloat) / 2;
1034           x2 = pv->X + (PIN_SIZE (pv) + 1 + Bloat) / 2;
1035           y1 = pv->Y - (PIN_SIZE (pv) + 1 + Bloat) / 2;
1036           y2 = pv->Y + (PIN_SIZE (pv) + 1 + Bloat) / 2;
1037           if (IsRectangleInPolygon (x1, y1, x2, y2, i->polygon)
1038               && ADD_PV_TO_LIST (pv, i->flag))
1039             longjmp (i->env, 1);
1040         }
1041       else if (TEST_FLAG (OCTAGONFLAG, pv))
1042         {
1043           POLYAREA *oct = OctagonPoly (pv->X, pv->Y, PIN_SIZE (pv) / 2);
1044           if (isects (oct, i->polygon, true) && ADD_PV_TO_LIST (pv, i->flag))
1045             longjmp (i->env, 1);
1046         }
1047       else
1048         {
1049           if (IsPointInPolygon
1050               (pv->X, pv->Y, PIN_SIZE (pv) * 0.5 + Bloat, i->polygon)
1051               && ADD_PV_TO_LIST (pv, i->flag))
1052             longjmp (i->env, 1);
1053         }
1054     }
1055   return 0;
1056 }
1057
1058 static int
1059 pv_rat_callback (const BoxType * b, void *cl)
1060 {
1061   PinType *pv = (PinType *) b;
1062   struct lo_info *i = (struct lo_info *) cl;
1063
1064   /* rats can't cause DRC so there is no early exit */
1065   if (!TEST_FLAG (i->flag, pv) && IS_PV_ON_RAT (pv, i->rat))
1066     ADD_PV_TO_LIST (pv, i->flag);
1067   return 0;
1068 }
1069
1070 /* ---------------------------------------------------------------------------
1071  * searches for new PVs that are connected to NEW LOs on the list
1072  * This routine updates the position counter of the lists too.
1073  */
1074 static bool
1075 LookupPVConnectionsToLOList (int flag, bool AndRats)
1076 {
1077   Cardinal layer_no;
1078   struct lo_info info;
1079
1080   info.flag = flag;
1081
1082   /* loop over all layers */
1083   for (layer_no = 0; layer_no < max_copper_layer; layer_no++)
1084     {
1085       LayerType *layer = LAYER_PTR (layer_no);
1086
1087       if (layer->no_drc)
1088                        continue;
1089       /* do nothing if there are no PV's */
1090       if (TotalP + TotalV == 0)
1091         {
1092           LineList[layer_no].Location = LineList[layer_no].Number;
1093           ArcList[layer_no].Location = ArcList[layer_no].Number;
1094           PolygonList[layer_no].Location = PolygonList[layer_no].Number;
1095           continue;
1096         }
1097
1098       /* check all lines */
1099       while (LineList[layer_no].Location < LineList[layer_no].Number)
1100         {
1101           BoxType search_box;
1102
1103           info.line = LINELIST_ENTRY (layer_no, LineList[layer_no].Location);
1104           search_box = expand_bounds ((BoxType *)info.line);
1105
1106           if (setjmp (info.env) == 0)
1107             r_search (PCB->Data->via_tree, &search_box, NULL,
1108                       pv_line_callback, &info);
1109           else
1110             return true;
1111           if (setjmp (info.env) == 0)
1112             r_search (PCB->Data->pin_tree, &search_box, NULL,
1113                       pv_line_callback, &info);
1114           else
1115             return true;
1116           LineList[layer_no].Location++;
1117         }
1118
1119       /* check all arcs */
1120       while (ArcList[layer_no].Location < ArcList[layer_no].Number)
1121         {
1122           BoxType search_box;
1123
1124           info.arc = ARCLIST_ENTRY (layer_no, ArcList[layer_no].Location);
1125           search_box = expand_bounds ((BoxType *)info.arc);
1126
1127           if (setjmp (info.env) == 0)
1128             r_search (PCB->Data->via_tree, &search_box, NULL,
1129                       pv_arc_callback, &info);
1130           else
1131             return true;
1132           if (setjmp (info.env) == 0)
1133             r_search (PCB->Data->pin_tree, &search_box, NULL,
1134                       pv_arc_callback, &info);
1135           else
1136             return true;
1137           ArcList[layer_no].Location++;
1138         }
1139
1140       /* now all polygons */
1141       info.layer = layer_no;
1142       while (PolygonList[layer_no].Location < PolygonList[layer_no].Number)
1143         {
1144           BoxType search_box;
1145
1146           info.polygon = POLYGONLIST_ENTRY (layer_no, PolygonList[layer_no].Location);
1147           search_box = expand_bounds ((BoxType *)info.polygon);
1148
1149           if (setjmp (info.env) == 0)
1150             r_search (PCB->Data->via_tree, &search_box, NULL,
1151                       pv_poly_callback, &info);
1152           else
1153             return true;
1154           if (setjmp (info.env) == 0)
1155             r_search (PCB->Data->pin_tree, &search_box, NULL,
1156                       pv_poly_callback, &info);
1157           else
1158             return true;
1159           PolygonList[layer_no].Location++;
1160         }
1161     }
1162
1163   /* loop over all pad-layers */
1164   for (layer_no = 0; layer_no < 2; layer_no++)
1165     {
1166       /* do nothing if there are no PV's */
1167       if (TotalP + TotalV == 0)
1168         {
1169           PadList[layer_no].Location = PadList[layer_no].Number;
1170           continue;
1171         }
1172
1173       /* check all pads; for a detailed description see
1174        * the handling of lines in this subroutine
1175        */
1176       while (PadList[layer_no].Location < PadList[layer_no].Number)
1177         {
1178           BoxType search_box;
1179
1180           info.pad = PADLIST_ENTRY (layer_no, PadList[layer_no].Location);
1181           search_box = expand_bounds ((BoxType *)info.pad);
1182
1183           if (setjmp (info.env) == 0)
1184             r_search (PCB->Data->via_tree, &search_box, NULL,
1185                       pv_pad_callback, &info);
1186           else
1187             return true;
1188           if (setjmp (info.env) == 0)
1189             r_search (PCB->Data->pin_tree, &search_box, NULL,
1190                       pv_pad_callback, &info);
1191           else
1192             return true;
1193           PadList[layer_no].Location++;
1194         }
1195     }
1196
1197   /* do nothing if there are no PV's */
1198   if (TotalP + TotalV == 0)
1199     RatList.Location = RatList.Number;
1200
1201   /* check all rat-lines */
1202   if (AndRats)
1203     {
1204       while (RatList.Location < RatList.Number)
1205         {
1206           info.rat = RATLIST_ENTRY (RatList.Location);
1207           r_search_pt (PCB->Data->via_tree, & info.rat->Point1, 1, NULL,
1208                     pv_rat_callback, &info);
1209           r_search_pt (PCB->Data->via_tree, & info.rat->Point2, 1, NULL,
1210                     pv_rat_callback, &info);
1211           r_search_pt (PCB->Data->pin_tree, & info.rat->Point1, 1, NULL,
1212                     pv_rat_callback, &info);
1213           r_search_pt (PCB->Data->pin_tree, & info.rat->Point2, 1, NULL,
1214                     pv_rat_callback, &info);
1215
1216           RatList.Location++;
1217         }
1218     }
1219   return (false);
1220 }
1221
1222 /* reduce arc start angle and delta to 0..360 */
1223 static void
1224 normalize_angles (Angle *sa, Angle *d)
1225 {
1226   if (*d < 0)
1227     {
1228       *sa += *d;
1229       *d = - *d;
1230     }
1231   if (*d > 360) /* full circle */
1232     *d = 360;
1233   *sa = NormalizeAngle (*sa);
1234 }
1235
1236 static int
1237 radius_crosses_arc (double x, double y, ArcType *arc)
1238 {
1239   double alpha = atan2 (y - arc->Y, -x + arc->X) * RAD_TO_DEG;
1240   Angle sa = arc->StartAngle, d = arc->Delta;
1241
1242   normalize_angles (&sa, &d);
1243   if (alpha < 0)
1244     alpha += 360;
1245   if (sa <= alpha)
1246     return (sa + d) >= alpha;
1247   return (sa + d - 360) >= alpha;
1248 }
1249
1250 static void
1251 get_arc_ends (Coord *box, ArcType *arc)
1252 {
1253   box[0] = arc->X - arc->Width  * cos (M180 * arc->StartAngle);
1254   box[1] = arc->Y + arc->Height * sin (M180 * arc->StartAngle);
1255   box[2] = arc->X - arc->Width  * cos (M180 * (arc->StartAngle + arc->Delta));
1256   box[3] = arc->Y + arc->Height * sin (M180 * (arc->StartAngle + arc->Delta));
1257 }
1258 /* ---------------------------------------------------------------------------
1259  * check if two arcs intersect
1260  * first we check for circle intersections,
1261  * then find the actual points of intersection
1262  * and test them to see if they are on arcs
1263  *
1264  * consider a, the distance from the center of arc 1
1265  * to the point perpendicular to the intersecting points.
1266  *
1267  *  a = (r1^2 - r2^2 + l^2)/(2l)
1268  *
1269  * the perpendicular distance to the point of intersection
1270  * is then
1271  *
1272  * d = sqrt(r1^2 - a^2)
1273  *
1274  * the points of intersection would then be
1275  *
1276  * x = X1 + a/l dx +- d/l dy
1277  * y = Y1 + a/l dy -+ d/l dx
1278  *
1279  * where dx = X2 - X1 and dy = Y2 - Y1
1280  *
1281  *
1282  */
1283 static bool
1284 ArcArcIntersect (ArcType *Arc1, ArcType *Arc2)
1285 {
1286   double x, y, dx, dy, r1, r2, a, d, l, t, t1, t2, dl;
1287   Coord pdx, pdy;
1288   Coord box[8];
1289
1290   t  = 0.5 * Arc1->Thickness + Bloat;
1291   t2 = 0.5 * Arc2->Thickness;
1292   t1 = t2 + Bloat;
1293
1294   /* too thin arc */
1295   if (t < 0 || t1 < 0)
1296     return false;
1297
1298   /* try the end points first */
1299   get_arc_ends (&box[0], Arc1);
1300   get_arc_ends (&box[4], Arc2);
1301   if (IsPointOnArc (box[0], box[1], t, Arc2)
1302       || IsPointOnArc (box[2], box[3], t, Arc2)
1303       || IsPointOnArc (box[4], box[5], t, Arc1)
1304       || IsPointOnArc (box[6], box[7], t, Arc1))
1305     return true;
1306
1307   pdx = Arc2->X - Arc1->X;
1308   pdy = Arc2->Y - Arc1->Y;
1309   dl = Distance (Arc1->X, Arc1->Y, Arc2->X, Arc2->Y);
1310   /* concentric arcs, simpler intersection conditions */
1311   if (dl < 0.5)
1312     {
1313       if ((Arc1->Width - t >= Arc2->Width - t2
1314            && Arc1->Width - t <= Arc2->Width + t2)
1315           || (Arc1->Width + t >= Arc2->Width - t2
1316               && Arc1->Width + t <= Arc2->Width + t2))
1317         {
1318           Angle sa1 = Arc1->StartAngle, d1 = Arc1->Delta;
1319           Angle sa2 = Arc2->StartAngle, d2 = Arc2->Delta;
1320           /* NB the endpoints have already been checked,
1321              so we just compare the angles */
1322
1323           normalize_angles (&sa1, &d1);
1324           normalize_angles (&sa2, &d2);
1325           /* sa1 == sa2 was caught when checking endpoints */
1326           if (sa1 > sa2)
1327             if (sa1 < sa2 + d2 || sa1 + d1 - 360 > sa2)
1328               return true;
1329           if (sa2 > sa1)
1330             if (sa2 < sa1 + d1 || sa2 + d2 - 360 > sa1)
1331               return true;
1332         }
1333       return false;
1334     }
1335   r1 = Arc1->Width;
1336   r2 = Arc2->Width;
1337   /* arcs centerlines are too far or too near */
1338   if (dl > r1 + r2 || dl + r1 < r2 || dl + r2 < r1)
1339     {
1340       /* check the nearest to the other arc's center point */
1341       dx = pdx * r1 / dl;
1342       dy = pdy * r1 / dl;
1343       if (dl + r1 < r2) /* Arc1 inside Arc2 */
1344         {
1345           dx = - dx;
1346           dy = - dy;
1347         }
1348
1349       if (radius_crosses_arc (Arc1->X + dx, Arc1->Y + dy, Arc1)
1350           && IsPointOnArc (Arc1->X + dx, Arc1->Y + dy, t, Arc2))
1351         return true;
1352
1353       dx = - pdx * r2 / dl;
1354       dy = - pdy * r2 / dl;
1355       if (dl + r2 < r1) /* Arc2 inside Arc1 */
1356         {
1357           dx = - dx;
1358           dy = - dy;
1359         }
1360
1361       if (radius_crosses_arc (Arc2->X + dx, Arc2->Y + dy, Arc2)
1362           && IsPointOnArc (Arc2->X + dx, Arc2->Y + dy, t1, Arc1))
1363         return true;
1364       return false;
1365     }
1366
1367   l = dl * dl;
1368   r1 *= r1;
1369   r2 *= r2;
1370   a = 0.5 * (r1 - r2 + l) / l;
1371   r1 = r1 / l;
1372   d = r1 - a * a;
1373   /* the circles are too far apart to touch or probably just touch:
1374      check the nearest point */
1375   if (d < 0)
1376     d = 0;
1377   else
1378     d = sqrt (d);
1379   x = Arc1->X + a * pdx;
1380   y = Arc1->Y + a * pdy;
1381   dx = d * pdx;
1382   dy = d * pdy;
1383   if (radius_crosses_arc (x + dy, y - dx, Arc1)
1384       && IsPointOnArc (x + dy, y - dx, t, Arc2))
1385     return true;
1386   if (radius_crosses_arc (x + dy, y - dx, Arc2)
1387       && IsPointOnArc (x + dy, y - dx, t1, Arc1))
1388     return true;
1389
1390   if (radius_crosses_arc (x - dy, y + dx, Arc1)
1391       && IsPointOnArc (x - dy, y + dx, t, Arc2))
1392     return true;
1393   if (radius_crosses_arc (x - dy, y + dx, Arc2)
1394       && IsPointOnArc (x - dy, y + dx, t1, Arc1))
1395     return true;
1396   return false;
1397 }
1398
1399 /* ---------------------------------------------------------------------------
1400  * Tests if point is same as line end point
1401  */
1402 static bool
1403 IsRatPointOnLineEnd (PointType *Point, LineType *Line)
1404 {
1405   if ((Point->X == Line->Point1.X
1406        && Point->Y == Line->Point1.Y)
1407       || (Point->X == Line->Point2.X && Point->Y == Line->Point2.Y))
1408     return (true);
1409   return (false);
1410 }
1411
1412 static void
1413 form_slanted_rectangle (PointType p[4], LineType *l)
1414 /* writes vertices of a squared line */
1415 {
1416    double dwx = 0, dwy = 0;
1417    if (l->Point1.Y == l->Point2.Y)
1418      dwx = l->Thickness / 2.0;
1419    else if (l->Point1.X == l->Point2.X)
1420      dwy = l->Thickness / 2.0;
1421    else
1422      {
1423        Coord dX = l->Point2.X - l->Point1.X;
1424        Coord dY = l->Point2.Y - l->Point1.Y;
1425        double r = Distance (l->Point1.X, l->Point1.Y, l->Point2.X, l->Point2.Y);
1426        dwx = l->Thickness / 2.0 / r * dX;
1427        dwy = l->Thickness / 2.0 / r * dY;
1428      }
1429     p[0].X = l->Point1.X - dwx + dwy; p[0].Y = l->Point1.Y - dwy - dwx;
1430     p[1].X = l->Point1.X - dwx - dwy; p[1].Y = l->Point1.Y - dwy + dwx;
1431     p[2].X = l->Point2.X + dwx - dwy; p[2].Y = l->Point2.Y + dwy + dwx;
1432     p[3].X = l->Point2.X + dwx + dwy; p[3].Y = l->Point2.Y + dwy - dwx;
1433 }
1434 /* ---------------------------------------------------------------------------
1435  * checks if two lines intersect
1436  * from news FAQ:
1437  *
1438  *  Let A,B,C,D be 2-space position vectors.  Then the directed line
1439  *  segments AB & CD are given by:
1440  *
1441  *      AB=A+r(B-A), r in [0,1]
1442  *      CD=C+s(D-C), s in [0,1]
1443  *
1444  *  If AB & CD intersect, then
1445  *
1446  *      A+r(B-A)=C+s(D-C), or
1447  *
1448  *      XA+r(XB-XA)=XC+s(XD-XC)
1449  *      YA+r(YB-YA)=YC+s(YD-YC)  for some r,s in [0,1]
1450  *
1451  *  Solving the above for r and s yields
1452  *
1453  *          (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
1454  *      r = -----------------------------  (eqn 1)
1455  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
1456  *
1457  *          (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
1458  *      s = -----------------------------  (eqn 2)
1459  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
1460  *
1461  *  Let I be the position vector of the intersection point, then
1462  *
1463  *      I=A+r(B-A) or
1464  *
1465  *      XI=XA+r(XB-XA)
1466  *      YI=YA+r(YB-YA)
1467  *
1468  *  By examining the values of r & s, you can also determine some
1469  *  other limiting conditions:
1470  *
1471  *      If 0<=r<=1 & 0<=s<=1, intersection exists
1472  *          r<0 or r>1 or s<0 or s>1 line segments do not intersect
1473  *
1474  *      If the denominator in eqn 1 is zero, AB & CD are parallel
1475  *      If the numerator in eqn 1 is also zero, AB & CD are coincident
1476  *
1477  *  If the intersection point of the 2 lines are needed (lines in this
1478  *  context mean infinite lines) regardless whether the two line
1479  *  segments intersect, then
1480  *
1481  *      If r>1, I is located on extension of AB
1482  *      If r<0, I is located on extension of BA
1483  *      If s>1, I is located on extension of CD
1484  *      If s<0, I is located on extension of DC
1485  *
1486  *  Also note that the denominators of eqn 1 & 2 are identical.
1487  *
1488  */
1489 bool
1490 LineLineIntersect (LineType *Line1, LineType *Line2)
1491 {
1492   double s, r;
1493   double line1_dx, line1_dy, line2_dx, line2_dy,
1494          point1_dx, point1_dy;
1495   if (TEST_FLAG (SQUAREFLAG, Line1))/* pretty reckless recursion */
1496     {
1497       PointType p[4];
1498       form_slanted_rectangle (p, Line1);
1499       return IsLineInQuadrangle (p, Line2);
1500     }
1501   /* here come only round Line1 because IsLineInQuadrangle()
1502      calls LineLineIntersect() with first argument rounded*/
1503   if (TEST_FLAG (SQUAREFLAG, Line2))
1504     {
1505       PointType p[4];
1506       form_slanted_rectangle (p, Line2);
1507       return IsLineInQuadrangle (p, Line1);
1508     }
1509   /* now all lines are round */
1510
1511   /* Check endpoints: this provides a quick exit, catches
1512    *  cases where the "real" lines don't intersect but the
1513    *  thick lines touch, and ensures that the dx/dy business
1514    *  below does not cause a divide-by-zero. */
1515   if (IsPointInPad (Line2->Point1.X, Line2->Point1.Y,
1516                     MAX (Line2->Thickness / 2 + Bloat, 0),
1517                     (PadType *) Line1)
1518        || IsPointInPad (Line2->Point2.X, Line2->Point2.Y,
1519                         MAX (Line2->Thickness / 2 + Bloat, 0),
1520                         (PadType *) Line1)
1521        || IsPointInPad (Line1->Point1.X, Line1->Point1.Y,
1522                         MAX (Line1->Thickness / 2 + Bloat, 0),
1523                         (PadType *) Line2)
1524        || IsPointInPad (Line1->Point2.X, Line1->Point2.Y,
1525                         MAX (Line1->Thickness / 2 + Bloat, 0),
1526                         (PadType *) Line2))
1527     return true;
1528
1529   /* setup some constants */
1530   line1_dx = Line1->Point2.X - Line1->Point1.X;
1531   line1_dy = Line1->Point2.Y - Line1->Point1.Y;
1532   line2_dx = Line2->Point2.X - Line2->Point1.X;
1533   line2_dy = Line2->Point2.Y - Line2->Point1.Y;
1534   point1_dx = Line1->Point1.X - Line2->Point1.X;
1535   point1_dy = Line1->Point1.Y - Line2->Point1.Y;
1536
1537   /* If either line is a point, we have failed already, since the
1538    *   endpoint check above will have caught an "intersection". */
1539   if ((line1_dx == 0 && line1_dy == 0)
1540       || (line2_dx == 0 && line2_dy == 0))
1541     return false;
1542
1543   /* set s to cross product of Line1 and the line
1544    *   Line1.Point1--Line2.Point1 (as vectors) */
1545   s = point1_dy * line1_dx - point1_dx * line1_dy;
1546
1547   /* set r to cross product of both lines (as vectors) */
1548   r = line1_dx * line2_dy - line1_dy * line2_dx;
1549
1550   /* No cross product means parallel lines, or maybe Line2 is
1551    *  zero-length. In either case, since we did a bounding-box
1552    *  check before getting here, the above IsPointInPad() checks
1553    *  will have caught any intersections. */
1554   if (r == 0.0)
1555     return false;
1556
1557   s /= r;
1558   r = (point1_dy * line2_dx - point1_dx * line2_dy) / r;
1559
1560   /* intersection is at least on AB */
1561   if (r >= 0.0 && r <= 1.0)
1562     return (s >= 0.0 && s <= 1.0);
1563
1564   /* intersection is at least on CD */
1565   /* [removed this case since it always returns false --asp] */
1566   return false;
1567 }
1568
1569 /*---------------------------------------------------
1570  *
1571  * Check for line intersection with an arc
1572  *
1573  * Mostly this is like the circle/line intersection
1574  * found in IsPointOnLine (search.c) see the detailed
1575  * discussion for the basics there.
1576  *
1577  * Since this is only an arc, not a full circle we need
1578  * to find the actual points of intersection with the
1579  * circle, and see if they are on the arc.
1580  *
1581  * To do this, we translate along the line from the point Q
1582  * plus or minus a distance delta = sqrt(Radius^2 - d^2)
1583  * but it's handy to normalize with respect to l, the line
1584  * length so a single projection is done (e.g. we don't first
1585  * find the point Q
1586  *
1587  * The projection is now of the form
1588  *
1589  *      Px = X1 + (r +- r2)(X2 - X1)
1590  *      Py = Y1 + (r +- r2)(Y2 - Y1)
1591  *
1592  * Where r2 sqrt(Radius^2 l^2 - d^2)/l^2
1593  * note that this is the variable d, not the symbol d described in IsPointOnLine
1594  * (variable d = symbol d * l)
1595  *
1596  * The end points are hell so they are checked individually
1597  */
1598 bool
1599 LineArcIntersect (LineType *Line, ArcType *Arc)
1600 {
1601   double dx, dy, dx1, dy1, l, d, r, r2, Radius;
1602   BoxType *box;
1603
1604   dx = Line->Point2.X - Line->Point1.X;
1605   dy = Line->Point2.Y - Line->Point1.Y;
1606   dx1 = Line->Point1.X - Arc->X;
1607   dy1 = Line->Point1.Y - Arc->Y;
1608   l = dx * dx + dy * dy;
1609   d = dx * dy1 - dy * dx1;
1610   d *= d;
1611
1612   /* use the larger diameter circle first */
1613   Radius =
1614     Arc->Width + MAX (0.5 * (Arc->Thickness + Line->Thickness) + Bloat, 0.0);
1615   Radius *= Radius;
1616   r2 = Radius * l - d;
1617   /* projection doesn't even intersect circle when r2 < 0 */
1618   if (r2 < 0)
1619     return (false);
1620   /* check the ends of the line in case the projected point */
1621   /* of intersection is beyond the line end */
1622   if (IsPointOnArc
1623       (Line->Point1.X, Line->Point1.Y,
1624        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1625     return (true);
1626   if (IsPointOnArc
1627       (Line->Point2.X, Line->Point2.Y,
1628        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1629     return (true);
1630   if (l == 0.0)
1631     return (false);
1632   r2 = sqrt (r2);
1633   Radius = -(dx * dx1 + dy * dy1);
1634   r = (Radius + r2) / l;
1635   if (r >= 0 && r <= 1
1636       && IsPointOnArc (Line->Point1.X + r * dx,
1637                        Line->Point1.Y + r * dy,
1638                        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1639     return (true);
1640   r = (Radius - r2) / l;
1641   if (r >= 0 && r <= 1
1642       && IsPointOnArc (Line->Point1.X + r * dx,
1643                        Line->Point1.Y + r * dy,
1644                        MAX (0.5 * Line->Thickness + Bloat, 0.0), Arc))
1645     return (true);
1646   /* check arc end points */
1647   box = GetArcEnds (Arc);
1648   if (IsPointInPad (box->X1, box->Y1, Arc->Thickness * 0.5 + Bloat, (PadType *)Line))
1649     return true;
1650   if (IsPointInPad (box->X2, box->Y2, Arc->Thickness * 0.5 + Bloat, (PadType *)Line))
1651     return true;
1652   return false;
1653 }
1654
1655 static int
1656 LOCtoArcLine_callback (const BoxType * b, void *cl)
1657 {
1658   LineType *line = (LineType *) b;
1659   struct lo_info *i = (struct lo_info *) cl;
1660
1661   if (!TEST_FLAG (i->flag, line) && LineArcIntersect (line, i->arc))
1662     {
1663       if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
1664         longjmp (i->env, 1);
1665     }
1666   return 0;
1667 }
1668
1669 static int
1670 LOCtoArcArc_callback (const BoxType * b, void *cl)
1671 {
1672   ArcType *arc = (ArcType *) b;
1673   struct lo_info *i = (struct lo_info *) cl;
1674
1675   if (!arc->Thickness)
1676     return 0;
1677   if (!TEST_FLAG (i->flag, arc) && ArcArcIntersect (i->arc, arc))
1678     {
1679       if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
1680         longjmp (i->env, 1);
1681     }
1682   return 0;
1683 }
1684
1685 static int
1686 LOCtoArcPad_callback (const BoxType * b, void *cl)
1687 {
1688   PadType *pad = (PadType *) b;
1689   struct lo_info *i = (struct lo_info *) cl;
1690
1691   if (!TEST_FLAG (i->flag, pad) && i->layer ==
1692       (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
1693       && ArcPadIntersect (i->arc, pad) && ADD_PAD_TO_LIST (i->layer, pad, i->flag))
1694     longjmp (i->env, 1);
1695   return 0;
1696 }
1697
1698 /* ---------------------------------------------------------------------------
1699  * searches all LOs that are connected to the given arc on the given
1700  * layergroup. All found connections are added to the list
1701  *
1702  * the notation that is used is:
1703  * Xij means Xj at arc i
1704  */
1705 static bool
1706 LookupLOConnectionsToArc (ArcType *Arc, Cardinal LayerGroup, int flag, bool AndRats)
1707 {
1708   Cardinal entry;
1709   struct lo_info info;
1710   BoxType search_box;
1711
1712   info.flag = flag;
1713   info.arc = Arc;
1714   search_box = expand_bounds ((BoxType *)info.arc);
1715
1716   /* loop over all layers of the group */
1717   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
1718     {
1719       Cardinal layer_no;
1720       LayerType *layer;
1721       GList *i;
1722
1723       layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
1724       layer = LAYER_PTR (layer_no);
1725
1726       /* handle normal layers */
1727       if (layer_no < max_copper_layer)
1728         {
1729           info.layer = layer_no;
1730           /* add arcs */
1731           if (setjmp (info.env) == 0)
1732             r_search (layer->line_tree, &search_box,
1733                       NULL, LOCtoArcLine_callback, &info);
1734           else
1735             return true;
1736
1737           if (setjmp (info.env) == 0)
1738             r_search (layer->arc_tree, &search_box,
1739                       NULL, LOCtoArcArc_callback, &info);
1740           else
1741             return true;
1742
1743           /* now check all polygons */
1744           for (i = layer->Polygon; i != NULL; i = g_list_next (i))
1745             {
1746               PolygonType *polygon = i->data;
1747               if (!TEST_FLAG (flag, polygon) && IsArcInPolygon (Arc, polygon)
1748                   && ADD_POLYGON_TO_LIST (layer_no, polygon, flag))
1749                 return true;
1750             }
1751         }
1752       else
1753         {
1754           info.layer = layer_no - max_copper_layer;
1755           if (setjmp (info.env) == 0)
1756             r_search (PCB->Data->pad_tree, &search_box, NULL,
1757                       LOCtoArcPad_callback, &info);
1758           else
1759             return true;
1760         }
1761     }
1762   return (false);
1763 }
1764
1765 static int
1766 LOCtoLineLine_callback (const BoxType * b, void *cl)
1767 {
1768   LineType *line = (LineType *) b;
1769   struct lo_info *i = (struct lo_info *) cl;
1770
1771   if (!TEST_FLAG (i->flag, line) && LineLineIntersect (i->line, line))
1772     {
1773       if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
1774         longjmp (i->env, 1);
1775     }
1776   return 0;
1777 }
1778
1779 static int
1780 LOCtoLineArc_callback (const BoxType * b, void *cl)
1781 {
1782   ArcType *arc = (ArcType *) b;
1783   struct lo_info *i = (struct lo_info *) cl;
1784
1785   if (!arc->Thickness)
1786     return 0;
1787   if (!TEST_FLAG (i->flag, arc) && LineArcIntersect (i->line, arc))
1788     {
1789       if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
1790         longjmp (i->env, 1);
1791     }
1792   return 0;
1793 }
1794
1795 static int
1796 LOCtoLineRat_callback (const BoxType * b, void *cl)
1797 {
1798   RatType *rat = (RatType *) b;
1799   struct lo_info *i = (struct lo_info *) cl;
1800
1801   if (!TEST_FLAG (i->flag, rat))
1802     {
1803       if ((rat->group1 == i->layer)
1804           && IsRatPointOnLineEnd (&rat->Point1, i->line))
1805         {
1806           if (ADD_RAT_TO_LIST (rat, i->flag))
1807             longjmp (i->env, 1);
1808         }
1809       else if ((rat->group2 == i->layer)
1810                && IsRatPointOnLineEnd (&rat->Point2, i->line))
1811         {
1812           if (ADD_RAT_TO_LIST (rat, i->flag))
1813             longjmp (i->env, 1);
1814         }
1815     }
1816   return 0;
1817 }
1818
1819 static int
1820 LOCtoLinePad_callback (const BoxType * b, void *cl)
1821 {
1822   PadType *pad = (PadType *) b;
1823   struct lo_info *i = (struct lo_info *) cl;
1824
1825   if (!TEST_FLAG (i->flag, pad) && i->layer ==
1826       (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
1827       && LinePadIntersect (i->line, pad) && ADD_PAD_TO_LIST (i->layer, pad, i->flag))
1828     longjmp (i->env, 1);
1829   return 0;
1830 }
1831
1832 /* ---------------------------------------------------------------------------
1833  * searches all LOs that are connected to the given line on the given
1834  * layergroup. All found connections are added to the list
1835  *
1836  * the notation that is used is:
1837  * Xij means Xj at line i
1838  */
1839 static bool
1840 LookupLOConnectionsToLine (LineType *Line, Cardinal LayerGroup,
1841                            int flag, bool PolysTo, bool AndRats)
1842 {
1843   Cardinal entry;
1844   struct lo_info info;
1845   BoxType search_box;
1846
1847   info.flag = flag;
1848   info.layer = LayerGroup;
1849   info.line = Line;
1850   search_box = expand_bounds ((BoxType *)info.line);
1851
1852   if (AndRats)
1853     {
1854       /* add the new rat lines */
1855       if (setjmp (info.env) == 0)
1856         r_search (PCB->Data->rat_tree, &search_box, NULL,
1857                   LOCtoLineRat_callback, &info);
1858       else
1859         return true;
1860     }
1861
1862   /* loop over all layers of the group */
1863   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
1864     {
1865       Cardinal layer_no;
1866       LayerType *layer;
1867
1868       layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
1869       layer = LAYER_PTR (layer_no);
1870
1871       /* handle normal layers */
1872       if (layer_no < max_copper_layer)
1873         {
1874           info.layer = layer_no;
1875           /* add lines */
1876           if (setjmp (info.env) == 0)
1877             r_search (layer->line_tree, &search_box,
1878                       NULL, LOCtoLineLine_callback, &info);
1879           else
1880             return true;
1881           /* add arcs */
1882           if (setjmp (info.env) == 0)
1883             r_search (layer->arc_tree, &search_box,
1884                       NULL, LOCtoLineArc_callback, &info);
1885           else
1886             return true;
1887           /* now check all polygons */
1888           if (PolysTo)
1889             {
1890               GList *i;
1891               for (i = layer->Polygon; i != NULL; i = g_list_next (i))
1892                 {
1893                   PolygonType *polygon = i->data;
1894                   if (!TEST_FLAG (flag, polygon) && IsLineInPolygon (Line, polygon)
1895                       && ADD_POLYGON_TO_LIST (layer_no, polygon, flag))
1896                     return true;
1897                 }
1898             }
1899         }
1900       else
1901         {
1902           /* handle special 'pad' layers */
1903           info.layer = layer_no - max_copper_layer;
1904           if (setjmp (info.env) == 0)
1905             r_search (PCB->Data->pad_tree, &search_box, NULL,
1906                       LOCtoLinePad_callback, &info);
1907           else
1908             return true;
1909         }
1910     }
1911   return (false);
1912 }
1913
1914 struct rat_info
1915 {
1916   Cardinal layer;
1917   PointType *Point;
1918   int flag;
1919   jmp_buf env;
1920 };
1921
1922 static int
1923 LOCtoRat_callback (const BoxType * b, void *cl)
1924 {
1925   LineType *line = (LineType *) b;
1926   struct rat_info *i = (struct rat_info *) cl;
1927
1928   if (!TEST_FLAG (i->flag, line) &&
1929       ((line->Point1.X == i->Point->X &&
1930         line->Point1.Y == i->Point->Y) ||
1931        (line->Point2.X == i->Point->X && line->Point2.Y == i->Point->Y)))
1932     {
1933       if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
1934         longjmp (i->env, 1);
1935     }
1936   return 0;
1937 }
1938 static int
1939 PolygonToRat_callback (const BoxType * b, void *cl)
1940 {
1941   PolygonType *polygon = (PolygonType *) b;
1942   struct rat_info *i = (struct rat_info *) cl;
1943
1944   if (!TEST_FLAG (i->flag, polygon) && polygon->Clipped &&
1945       (i->Point->X == polygon->Clipped->contours->head.point[0]) &&
1946       (i->Point->Y == polygon->Clipped->contours->head.point[1]))
1947     {
1948       if (ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
1949         longjmp (i->env, 1);
1950     }
1951   return 0;
1952 }
1953
1954 static int
1955 LOCtoPad_callback (const BoxType * b, void *cl)
1956 {
1957   PadType *pad = (PadType *) b;
1958   struct rat_info *i = (struct rat_info *) cl;
1959
1960   if (!TEST_FLAG (i->flag, pad) && i->layer ==
1961         (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE) &&
1962       ((pad->Point1.X == i->Point->X && pad->Point1.Y == i->Point->Y) ||
1963        (pad->Point2.X == i->Point->X && pad->Point2.Y == i->Point->Y) ||
1964        ((pad->Point1.X + pad->Point2.X) / 2 == i->Point->X &&
1965         (pad->Point1.Y + pad->Point2.Y) / 2 == i->Point->Y)) &&
1966       ADD_PAD_TO_LIST (i->layer, pad, i->flag))
1967     longjmp (i->env, 1);
1968   return 0;
1969 }
1970
1971 /* ---------------------------------------------------------------------------
1972  * searches all LOs that are connected to the given rat-line on the given
1973  * layergroup. All found connections are added to the list
1974  *
1975  * the notation that is used is:
1976  * Xij means Xj at line i
1977  */
1978 static bool
1979 LookupLOConnectionsToRatEnd (PointType *Point, Cardinal LayerGroup, int flag)
1980 {
1981   Cardinal entry;
1982   struct rat_info info;
1983
1984   info.flag = flag;
1985   info.Point = Point;
1986   /* loop over all layers of this group */
1987   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
1988     {
1989       Cardinal layer_no;
1990       LayerType *layer;
1991
1992       layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
1993       layer = LAYER_PTR (layer_no);
1994       /* handle normal layers
1995          rats don't ever touch
1996          arcs by definition
1997        */
1998
1999       if (layer_no < max_copper_layer)
2000         {
2001           info.layer = layer_no;
2002           if (setjmp (info.env) == 0)
2003             r_search_pt (layer->line_tree, Point, 1, NULL,
2004                       LOCtoRat_callback, &info);
2005           else
2006             return true;
2007           if (setjmp (info.env) == 0)
2008             r_search_pt (layer->polygon_tree, Point, 1,
2009                       NULL, PolygonToRat_callback, &info);
2010         }
2011       else
2012         {
2013           /* handle special 'pad' layers */
2014           info.layer = layer_no - max_copper_layer;
2015           if (setjmp (info.env) == 0)
2016             r_search_pt (PCB->Data->pad_tree, Point, 1, NULL,
2017                       LOCtoPad_callback, &info);
2018           else
2019             return true;
2020         }
2021     }
2022   return (false);
2023 }
2024
2025 static int
2026 LOCtoPadLine_callback (const BoxType * b, void *cl)
2027 {
2028   LineType *line = (LineType *) b;
2029   struct lo_info *i = (struct lo_info *) cl;
2030
2031   if (!TEST_FLAG (i->flag, line) && LinePadIntersect (line, i->pad))
2032     {
2033       if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2034         longjmp (i->env, 1);
2035     }
2036   return 0;
2037 }
2038
2039 static int
2040 LOCtoPadArc_callback (const BoxType * b, void *cl)
2041 {
2042   ArcType *arc = (ArcType *) b;
2043   struct lo_info *i = (struct lo_info *) cl;
2044
2045   if (!arc->Thickness)
2046     return 0;
2047   if (!TEST_FLAG (i->flag, arc) && ArcPadIntersect (arc, i->pad))
2048     {
2049       if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
2050         longjmp (i->env, 1);
2051     }
2052   return 0;
2053 }
2054
2055 static int
2056 LOCtoPadPoly_callback (const BoxType * b, void *cl)
2057 {
2058   PolygonType *polygon = (PolygonType *) b;
2059   struct lo_info *i = (struct lo_info *) cl;
2060
2061
2062   if (!TEST_FLAG (i->flag, polygon) &&
2063       (!TEST_FLAG (CLEARPOLYFLAG, polygon) || !i->pad->Clearance))
2064     {
2065       if (IsPadInPolygon (i->pad, polygon) &&
2066           ADD_POLYGON_TO_LIST (i->layer, polygon, i->flag))
2067         longjmp (i->env, 1);
2068     }
2069   return 0;
2070 }
2071
2072 static int
2073 LOCtoPadRat_callback (const BoxType * b, void *cl)
2074 {
2075   RatType *rat = (RatType *) b;
2076   struct lo_info *i = (struct lo_info *) cl;
2077
2078   if (!TEST_FLAG (i->flag, rat))
2079     {
2080       if (rat->group1 == i->layer &&
2081           ((rat->Point1.X == i->pad->Point1.X && rat->Point1.Y == i->pad->Point1.Y) ||
2082            (rat->Point1.X == i->pad->Point2.X && rat->Point1.Y == i->pad->Point2.Y) ||
2083            (rat->Point1.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
2084             rat->Point1.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2)))
2085         {
2086           if (ADD_RAT_TO_LIST (rat, i->flag))
2087             longjmp (i->env, 1);
2088         }
2089       else if (rat->group2 == i->layer &&
2090                ((rat->Point2.X == i->pad->Point1.X && rat->Point2.Y == i->pad->Point1.Y) ||
2091                 (rat->Point2.X == i->pad->Point2.X && rat->Point2.Y == i->pad->Point2.Y) ||
2092                 (rat->Point2.X == (i->pad->Point1.X + i->pad->Point2.X) / 2 &&
2093                  rat->Point2.Y == (i->pad->Point1.Y + i->pad->Point2.Y) / 2)))
2094         {
2095           if (ADD_RAT_TO_LIST (rat, i->flag))
2096             longjmp (i->env, 1);
2097         }
2098     }
2099   return 0;
2100 }
2101
2102 static int
2103 LOCtoPadPad_callback (const BoxType * b, void *cl)
2104 {
2105   PadType *pad = (PadType *) b;
2106   struct lo_info *i = (struct lo_info *) cl;
2107
2108   if (!TEST_FLAG (i->flag, pad) && i->layer ==
2109       (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
2110       && PadPadIntersect (pad, i->pad) && ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2111     longjmp (i->env, 1);
2112   return 0;
2113 }
2114
2115 /* ---------------------------------------------------------------------------
2116  * searches all LOs that are connected to the given pad on the given
2117  * layergroup. All found connections are added to the list
2118  */
2119 static bool
2120 LookupLOConnectionsToPad (PadType *Pad, Cardinal LayerGroup, int flag, bool AndRats)
2121 {
2122   Cardinal entry;
2123   struct lo_info info;
2124   BoxType search_box;
2125
2126   if (!TEST_FLAG (SQUAREFLAG, Pad))
2127     return (LookupLOConnectionsToLine ((LineType *) Pad, LayerGroup, flag, false, AndRats));
2128
2129   info.flag = flag;
2130   info.pad = Pad;
2131   search_box = expand_bounds ((BoxType *)info.pad);
2132
2133   /* add the new rat lines */
2134   info.layer = LayerGroup;
2135
2136   if (AndRats)
2137     {
2138       if (setjmp (info.env) == 0)
2139         r_search (PCB->Data->rat_tree, &search_box, NULL,
2140                   LOCtoPadRat_callback, &info);
2141       else
2142         return true;
2143     }
2144
2145   /* loop over all layers of the group */
2146   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2147     {
2148       Cardinal layer_no;
2149       LayerType *layer;
2150
2151       layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2152       layer = LAYER_PTR (layer_no);
2153       /* handle normal layers */
2154       if (layer_no < max_copper_layer)
2155         {
2156           info.layer = layer_no;
2157           /* add lines */
2158           if (setjmp (info.env) == 0)
2159             r_search (layer->line_tree, &search_box,
2160                       NULL, LOCtoPadLine_callback, &info);
2161           else
2162             return true;
2163           /* add arcs */
2164           if (setjmp (info.env) == 0)
2165             r_search (layer->arc_tree, &search_box,
2166                       NULL, LOCtoPadArc_callback, &info);
2167           else
2168             return true;
2169           /* add polygons */
2170           if (setjmp (info.env) == 0)
2171             r_search (layer->polygon_tree, &search_box,
2172                       NULL, LOCtoPadPoly_callback, &info);
2173           else
2174             return true;
2175         }
2176       else
2177         {
2178           /* handle special 'pad' layers */
2179           info.layer = layer_no - max_copper_layer;
2180           if (setjmp (info.env) == 0)
2181             r_search (PCB->Data->pad_tree, &search_box, NULL,
2182                       LOCtoPadPad_callback, &info);
2183           else
2184             return true;
2185         }
2186
2187     }
2188   return (false);
2189 }
2190
2191 static int
2192 LOCtoPolyLine_callback (const BoxType * b, void *cl)
2193 {
2194   LineType *line = (LineType *) b;
2195   struct lo_info *i = (struct lo_info *) cl;
2196
2197   if (!TEST_FLAG (i->flag, line) && IsLineInPolygon (line, i->polygon))
2198     {
2199       if (ADD_LINE_TO_LIST (i->layer, line, i->flag))
2200         longjmp (i->env, 1);
2201     }
2202   return 0;
2203 }
2204
2205 static int
2206 LOCtoPolyArc_callback (const BoxType * b, void *cl)
2207 {
2208   ArcType *arc = (ArcType *) b;
2209   struct lo_info *i = (struct lo_info *) cl;
2210
2211   if (!arc->Thickness)
2212     return 0;
2213   if (!TEST_FLAG (i->flag, arc) && IsArcInPolygon (arc, i->polygon))
2214     {
2215       if (ADD_ARC_TO_LIST (i->layer, arc, i->flag))
2216         longjmp (i->env, 1);
2217     }
2218   return 0;
2219 }
2220
2221 static int
2222 LOCtoPolyPad_callback (const BoxType * b, void *cl)
2223 {
2224   PadType *pad = (PadType *) b;
2225   struct lo_info *i = (struct lo_info *) cl;
2226
2227   if (!TEST_FLAG (i->flag, pad) && i->layer ==
2228       (TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE)
2229       && IsPadInPolygon (pad, i->polygon))
2230     {
2231       if (ADD_PAD_TO_LIST (i->layer, pad, i->flag))
2232         longjmp (i->env, 1);
2233     }
2234   return 0;
2235 }
2236
2237 static int
2238 LOCtoPolyRat_callback (const BoxType * b, void *cl)
2239 {
2240   RatType *rat = (RatType *) b;
2241   struct lo_info *i = (struct lo_info *) cl;
2242
2243   if (!TEST_FLAG (i->flag, rat))
2244     {
2245       if ((rat->Point1.X == (i->polygon->Clipped->contours->head.point[0]) &&
2246            rat->Point1.Y == (i->polygon->Clipped->contours->head.point[1]) &&
2247            rat->group1 == i->layer) ||
2248           (rat->Point2.X == (i->polygon->Clipped->contours->head.point[0]) &&
2249            rat->Point2.Y == (i->polygon->Clipped->contours->head.point[1]) &&
2250            rat->group2 == i->layer))
2251         if (ADD_RAT_TO_LIST (rat, i->flag))
2252           longjmp (i->env, 1);
2253     }
2254   return 0;
2255 }
2256
2257
2258 /* ---------------------------------------------------------------------------
2259  * looks up LOs that are connected to the given polygon
2260  * on the given layergroup. All found connections are added to the list
2261  */
2262 static bool
2263 LookupLOConnectionsToPolygon (PolygonType *Polygon, Cardinal LayerGroup, int flag, bool AndRats)
2264 {
2265   Cardinal entry;
2266   struct lo_info info;
2267   BoxType search_box;
2268
2269   if (!Polygon->Clipped)
2270     return false;
2271
2272   info.flag = flag;
2273   info.polygon = Polygon;
2274   search_box = expand_bounds ((BoxType *)info.polygon);
2275
2276   info.layer = LayerGroup;
2277
2278   /* check rats */
2279   if (AndRats)
2280     {
2281       if (setjmp (info.env) == 0)
2282         r_search (PCB->Data->rat_tree, &search_box, NULL,
2283                   LOCtoPolyRat_callback, &info);
2284       else
2285         return true;
2286     }
2287
2288 /* loop over all layers of the group */
2289   for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
2290     {
2291       Cardinal layer_no;
2292       LayerType *layer;
2293
2294       layer_no = PCB->LayerGroups.Entries[LayerGroup][entry];
2295       layer = LAYER_PTR (layer_no);
2296
2297       /* handle normal layers */
2298       if (layer_no < max_copper_layer)
2299         {
2300           GList *i;
2301
2302           /* check all polygons */
2303           for (i = layer->Polygon; i != NULL; i = g_list_next (i))
2304             {
2305               PolygonType *polygon = i->data;
2306               if (!TEST_FLAG (flag, polygon)
2307                   && IsPolygonInPolygon (polygon, Polygon)
2308                   && ADD_POLYGON_TO_LIST (layer_no, polygon, flag))
2309                 return true;
2310             }
2311
2312           info.layer = layer_no;
2313           /* check all lines */
2314           if (setjmp (info.env) == 0)
2315             r_search (layer->line_tree, &search_box,
2316                       NULL, LOCtoPolyLine_callback, &info);
2317           else
2318             return true;
2319           /* check all arcs */
2320           if (setjmp (info.env) == 0)
2321             r_search (layer->arc_tree, &search_box,
2322                       NULL, LOCtoPolyArc_callback, &info);
2323           else
2324             return true;
2325         }
2326       else
2327         {
2328           info.layer = layer_no - max_copper_layer;
2329           if (setjmp (info.env) == 0)
2330             r_search (PCB->Data->pad_tree, &search_box,
2331                       NULL, LOCtoPolyPad_callback, &info);
2332           else
2333             return true;
2334         }
2335     }
2336   return (false);
2337 }
2338
2339 /* ---------------------------------------------------------------------------
2340  * checks if an arc has a connection to a polygon
2341  *
2342  * - first check if the arc can intersect with the polygon by
2343  *   evaluating the bounding boxes
2344  * - check the two end points of the arc. If none of them matches
2345  * - check all segments of the polygon against the arc.
2346  */
2347 static bool
2348 IsArcInPolygon (ArcType *Arc, PolygonType *Polygon)
2349 {
2350   BoxType *Box = (BoxType *) Arc;
2351
2352   /* arcs with clearance never touch polys */
2353   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Arc))
2354     return false;
2355   if (!Polygon->Clipped)
2356     return false;
2357   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2358       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2359       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2360       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2361     {
2362       POLYAREA *ap;
2363
2364       if (!(ap = ArcPoly (Arc, Arc->Thickness + Bloat)))
2365         return false;           /* error */
2366       return isects (ap, Polygon, true);
2367     }
2368   return false;
2369 }
2370
2371 /* ---------------------------------------------------------------------------
2372  * checks if a line has a connection to a polygon
2373  *
2374  * - first check if the line can intersect with the polygon by
2375  *   evaluating the bounding boxes
2376  * - check the two end points of the line. If none of them matches
2377  * - check all segments of the polygon against the line.
2378  */
2379 static bool
2380 IsLineInPolygon (LineType *Line, PolygonType *Polygon)
2381 {
2382   BoxType *Box = (BoxType *) Line;
2383   POLYAREA *lp;
2384
2385   /* lines with clearance never touch polygons */
2386   if (TEST_FLAG (CLEARPOLYFLAG, Polygon) && TEST_FLAG (CLEARLINEFLAG, Line))
2387     return false;
2388   if (!Polygon->Clipped)
2389     return false;
2390   if (TEST_FLAG(SQUAREFLAG,Line)&&(Line->Point1.X==Line->Point2.X||Line->Point1.Y==Line->Point2.Y))
2391      {
2392        Coord wid = (Line->Thickness + Bloat + 1) / 2;
2393        Coord x1, x2, y1, y2;
2394
2395        x1 = MIN (Line->Point1.X, Line->Point2.X) - wid;
2396        y1 = MIN (Line->Point1.Y, Line->Point2.Y) - wid;
2397        x2 = MAX (Line->Point1.X, Line->Point2.X) + wid;
2398        y2 = MAX (Line->Point1.Y, Line->Point2.Y) + wid;
2399        return IsRectangleInPolygon (x1, y1, x2, y2, Polygon);
2400      }
2401   if (Box->X1 <= Polygon->Clipped->contours->xmax + Bloat
2402       && Box->X2 >= Polygon->Clipped->contours->xmin - Bloat
2403       && Box->Y1 <= Polygon->Clipped->contours->ymax + Bloat
2404       && Box->Y2 >= Polygon->Clipped->contours->ymin - Bloat)
2405     {
2406       if (!(lp = LinePoly (Line, Line->Thickness + Bloat)))
2407         return FALSE;           /* error */
2408       return isects (lp, Polygon, true);
2409     }
2410   return false;
2411 }
2412
2413 /* ---------------------------------------------------------------------------
2414  * checks if a pad connects to a non-clearing polygon
2415  *
2416  * The polygon is assumed to already have been proven non-clearing
2417  */
2418 static bool
2419 IsPadInPolygon (PadType *pad, PolygonType *polygon)
2420 {
2421     return IsLineInPolygon ((LineType *) pad, polygon);
2422 }
2423
2424 /* ---------------------------------------------------------------------------
2425  * checks if a polygon has a connection to a second one
2426  *
2427  * First check all points out of P1 against P2 and vice versa.
2428  * If both fail check all lines of P1 against the ones of P2
2429  */
2430 static bool
2431 IsPolygonInPolygon (PolygonType *P1, PolygonType *P2)
2432 {
2433   if (!P1->Clipped || !P2->Clipped)
2434     return false;
2435   assert (P1->Clipped->contours);
2436   assert (P2->Clipped->contours);
2437
2438   /* first check if both bounding boxes intersect. If not, return quickly */
2439   if (P1->Clipped->contours->xmin - Bloat > P2->Clipped->contours->xmax ||
2440       P1->Clipped->contours->xmax + Bloat < P2->Clipped->contours->xmin ||
2441       P1->Clipped->contours->ymin - Bloat > P2->Clipped->contours->ymax ||
2442       P1->Clipped->contours->ymax + Bloat < P2->Clipped->contours->ymin)
2443     return false;
2444
2445   /* first check un-bloated case */
2446   if (isects (P1->Clipped, P2, false))
2447     return TRUE;
2448
2449   /* now the difficult case of bloated */
2450   if (Bloat > 0)
2451     {
2452       PLINE *c;
2453       for (c = P1->Clipped->contours; c; c = c->next)
2454         {
2455           LineType line;
2456           VNODE *v = &c->head;
2457           if (c->xmin - Bloat <= P2->Clipped->contours->xmax &&
2458               c->xmax + Bloat >= P2->Clipped->contours->xmin &&
2459               c->ymin - Bloat <= P2->Clipped->contours->ymax &&
2460               c->ymax + Bloat >= P2->Clipped->contours->ymin)
2461             {
2462
2463               line.Point1.X = v->point[0];
2464               line.Point1.Y = v->point[1];
2465               line.Thickness = 2 * Bloat;
2466               line.Clearance = 0;
2467               line.Flags = NoFlags ();
2468               for (v = v->next; v != &c->head; v = v->next)
2469                 {
2470                   line.Point2.X = v->point[0];
2471                   line.Point2.Y = v->point[1];
2472                   SetLineBoundingBox (&line);
2473                   if (IsLineInPolygon (&line, P2))
2474                     return (true);
2475                   line.Point1.X = line.Point2.X;
2476                   line.Point1.Y = line.Point2.Y;
2477                 }
2478             }
2479         }
2480     }
2481
2482   return (false);
2483 }
2484
2485 /* ---------------------------------------------------------------------------
2486  * writes the several names of an element to a file
2487  */
2488 static void
2489 PrintElementNameList (ElementType *Element, FILE * FP)
2490 {
2491   static DynamicStringType cname, pname, vname;
2492
2493   CreateQuotedString (&cname, (char *)EMPTY (DESCRIPTION_NAME (Element)));
2494   CreateQuotedString (&pname, (char *)EMPTY (NAMEONPCB_NAME (Element)));
2495   CreateQuotedString (&vname, (char *)EMPTY (VALUE_NAME (Element)));
2496   fprintf (FP, "(%s %s %s)\n", cname.Data, pname.Data, vname.Data);
2497 }
2498
2499 /* ---------------------------------------------------------------------------
2500  * writes the several names of an element to a file
2501  */
2502 static void
2503 PrintConnectionElementName (ElementType *Element, FILE * FP)
2504 {
2505   fputs ("Element", FP);
2506   PrintElementNameList (Element, FP);
2507   fputs ("{\n", FP);
2508 }
2509
2510 /* ---------------------------------------------------------------------------
2511  * prints one {pin,pad,via}/element entry of connection lists
2512  */
2513 static void
2514 PrintConnectionListEntry (char *ObjName, ElementType *Element,
2515                           bool FirstOne, FILE * FP)
2516 {
2517   static DynamicStringType oname;
2518
2519   CreateQuotedString (&oname, ObjName);
2520   if (FirstOne)
2521     fprintf (FP, "\t%s\n\t{\n", oname.Data);
2522   else
2523     {
2524       fprintf (FP, "\t\t%s ", oname.Data);
2525       if (Element)
2526         PrintElementNameList (Element, FP);
2527       else
2528         fputs ("(__VIA__)\n", FP);
2529     }
2530 }
2531
2532 /* ---------------------------------------------------------------------------
2533  * prints all found connections of a pads to file FP
2534  * the connections are stacked in 'PadList'
2535  */
2536 static void
2537 PrintPadConnections (Cardinal Layer, FILE * FP, bool IsFirst)
2538 {
2539   Cardinal i;
2540   PadType *ptr;
2541
2542   if (!PadList[Layer].Number)
2543     return;
2544
2545   /* the starting pad */
2546   if (IsFirst)
2547     {
2548       ptr = PADLIST_ENTRY (Layer, 0);
2549       if (ptr != NULL)
2550         PrintConnectionListEntry ((char *)UNKNOWN (ptr->Name), NULL, true, FP);
2551       else
2552         printf ("Skipping NULL ptr in 1st part of PrintPadConnections\n");
2553     }
2554
2555   /* we maybe have to start with i=1 if we are handling the
2556    * starting-pad itself
2557    */
2558   for (i = IsFirst ? 1 : 0; i < PadList[Layer].Number; i++)
2559     {
2560       ptr = PADLIST_ENTRY (Layer, i);
2561       if (ptr != NULL)
2562         PrintConnectionListEntry ((char *)EMPTY (ptr->Name), (ElementType *)ptr->Element, false, FP);
2563       else
2564         printf ("Skipping NULL ptr in 2nd part of PrintPadConnections\n");
2565     }
2566 }
2567
2568 /* ---------------------------------------------------------------------------
2569  * prints all found connections of a pin to file FP
2570  * the connections are stacked in 'PVList'
2571  */
2572 static void
2573 PrintPinConnections (FILE * FP, bool IsFirst)
2574 {
2575   Cardinal i;
2576   PinType *pv;
2577
2578   if (!PVList.Number)
2579     return;
2580
2581   if (IsFirst)
2582     {
2583       /* the starting pin */
2584       pv = PVLIST_ENTRY (0);
2585       PrintConnectionListEntry ((char *)EMPTY (pv->Name), NULL, true, FP);
2586     }
2587
2588   /* we maybe have to start with i=1 if we are handling the
2589    * starting-pin itself
2590    */
2591   for (i = IsFirst ? 1 : 0; i < PVList.Number; i++)
2592     {
2593       /* get the elements name or assume that its a via */
2594       pv = PVLIST_ENTRY (i);
2595       PrintConnectionListEntry ((char *)EMPTY (pv->Name), (ElementType *)pv->Element, false, FP);
2596     }
2597 }
2598
2599 /* ---------------------------------------------------------------------------
2600  * checks if all lists of new objects are handled
2601  */
2602 static bool
2603 ListsEmpty (bool AndRats)
2604 {
2605   bool empty;
2606   int i;
2607
2608   empty = (PVList.Location >= PVList.Number);
2609   if (AndRats)
2610     empty = empty && (RatList.Location >= RatList.Number);
2611   for (i = 0; i < max_copper_layer && empty; i++)
2612     if (!LAYER_PTR (i)->no_drc)
2613       empty = empty && LineList[i].Location >= LineList[i].Number
2614         && ArcList[i].Location >= ArcList[i].Number
2615         && PolygonList[i].Location >= PolygonList[i].Number;
2616   return (empty);
2617 }
2618
2619 static void
2620 reassign_no_drc_flags (void)
2621 {
2622   int layer;
2623
2624   for (layer = 0; layer < max_copper_layer; layer++)
2625     {
2626       LayerType *l = LAYER_PTR (layer);
2627       l->no_drc = AttributeGet (l, "PCB::skip-drc") != NULL;
2628     }
2629 }
2630
2631
2632
2633
2634 /* ---------------------------------------------------------------------------
2635  * loops till no more connections are found
2636  */
2637 static bool
2638 DoIt (int flag, bool AndRats, bool AndDraw)
2639 {
2640   bool newone = false;
2641   reassign_no_drc_flags ();
2642   do
2643     {
2644       /* lookup connections; these are the steps (2) to (4)
2645        * from the description
2646        */
2647       newone = LookupPVConnectionsToPVList (flag) ||
2648                LookupLOConnectionsToPVList (flag, AndRats) ||
2649                LookupLOConnectionsToLOList (flag, AndRats) ||
2650                LookupPVConnectionsToLOList (flag, AndRats);
2651       if (AndDraw)
2652         DrawNewConnections ();
2653     }
2654   while (!newone && !ListsEmpty (AndRats));
2655   if (AndDraw)
2656     Draw ();
2657   return (newone);
2658 }
2659
2660 /* ---------------------------------------------------------------------------
2661  * prints all unused pins of an element to file FP
2662  */
2663 static bool
2664 PrintAndSelectUnusedPinsAndPadsOfElement (ElementType *Element, FILE * FP, int flag)
2665 {
2666   bool first = true;
2667   Cardinal number;
2668   static DynamicStringType oname;
2669
2670   /* check all pins in element */
2671
2672   PIN_LOOP (Element);
2673   {
2674     if (!TEST_FLAG (HOLEFLAG, pin))
2675       {
2676         /* pin might have bee checked before, add to list if not */
2677         if (!TEST_FLAG (flag, pin) && FP)
2678           {
2679             int i;
2680             if (ADD_PV_TO_LIST (pin, flag))
2681               return true;
2682             DoIt (flag, true, true);
2683             number = PadList[TOP_SIDE].Number
2684               + PadList[BOTTOM_SIDE].Number + PVList.Number;
2685             /* the pin has no connection if it's the only
2686              * list entry; don't count vias
2687              */
2688             for (i = 0; i < PVList.Number; i++)
2689               if (!PVLIST_ENTRY (i)->Element)
2690                 number--;
2691             if (number == 1)
2692               {
2693                 /* output of element name if not already done */
2694                 if (first)
2695                   {
2696                     PrintConnectionElementName (Element, FP);
2697                     first = false;
2698                   }
2699
2700                 /* write name to list and draw selected object */
2701                 CreateQuotedString (&oname, (char *)EMPTY (pin->Name));
2702                 fprintf (FP, "\t%s\n", oname.Data);
2703                 SET_FLAG (SELECTEDFLAG, pin);
2704                 DrawPin (pin);
2705               }
2706
2707             /* reset found objects for the next pin */
2708             if (PrepareNextLoop (FP))
2709               return (true);
2710           }
2711       }
2712   }
2713   END_LOOP;
2714
2715   /* check all pads in element */
2716   PAD_LOOP (Element);
2717   {
2718     /* lookup pad in list */
2719     /* pad might has bee checked before, add to list if not */
2720     if (!TEST_FLAG (flag, pad) && FP)
2721       {
2722         int i;
2723         if (ADD_PAD_TO_LIST (TEST_FLAG (ONSOLDERFLAG, pad)
2724                              ? BOTTOM_SIDE : TOP_SIDE, pad, flag))
2725           return true;
2726         DoIt (flag, true, true);
2727         number = PadList[TOP_SIDE].Number
2728           + PadList[BOTTOM_SIDE].Number + PVList.Number;
2729         /* the pin has no connection if it's the only
2730          * list entry; don't count vias
2731          */
2732         for (i = 0; i < PVList.Number; i++)
2733           if (!PVLIST_ENTRY (i)->Element)
2734             number--;
2735         if (number == 1)
2736           {
2737             /* output of element name if not already done */
2738             if (first)
2739               {
2740                 PrintConnectionElementName (Element, FP);
2741                 first = false;
2742               }
2743
2744             /* write name to list and draw selected object */
2745             CreateQuotedString (&oname, (char *)EMPTY (pad->Name));
2746             fprintf (FP, "\t%s\n", oname.Data);
2747             SET_FLAG (SELECTEDFLAG, pad);
2748             DrawPad (pad);
2749           }
2750
2751         /* reset found objects for the next pin */
2752         if (PrepareNextLoop (FP))
2753           return (true);
2754       }
2755   }
2756   END_LOOP;
2757
2758   /* print separator if element has unused pins or pads */
2759   if (!first)
2760     {
2761       fputs ("}\n\n", FP);
2762       SEPARATE (FP);
2763     }
2764   return (false);
2765 }
2766
2767 /* ---------------------------------------------------------------------------
2768  * resets some flags for looking up the next pin/pad
2769  */
2770 static bool
2771 PrepareNextLoop (FILE * FP)
2772 {
2773   Cardinal layer;
2774
2775   /* reset found LOs for the next pin */
2776   for (layer = 0; layer < max_copper_layer; layer++)
2777     {
2778       LineList[layer].Location = LineList[layer].Number = 0;
2779       ArcList[layer].Location = ArcList[layer].Number = 0;
2780       PolygonList[layer].Location = PolygonList[layer].Number = 0;
2781     }
2782
2783   /* reset found pads */
2784   for (layer = 0; layer < 2; layer++)
2785     PadList[layer].Location = PadList[layer].Number = 0;
2786
2787   /* reset PVs */
2788   PVList.Number = PVList.Location = 0;
2789   RatList.Number = RatList.Location = 0;
2790
2791   return (false);
2792 }
2793
2794 /* ---------------------------------------------------------------------------
2795  * finds all connections to the pins of the passed element.
2796  * The result is written to file FP
2797  * Returns true if operation was aborted
2798  */
2799 static bool
2800 PrintElementConnections (ElementType *Element, FILE * FP, int flag, bool AndDraw)
2801 {
2802   PrintConnectionElementName (Element, FP);
2803
2804   /* check all pins in element */
2805   PIN_LOOP (Element);
2806   {
2807     /* pin might have been checked before, add to list if not */
2808     if (TEST_FLAG (flag, pin))
2809       {
2810         PrintConnectionListEntry ((char *)EMPTY (pin->Name), NULL, true, FP);
2811         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
2812         continue;
2813       }
2814     if (ADD_PV_TO_LIST (pin, flag))
2815       return true;
2816     DoIt (flag, true, AndDraw);
2817     /* printout all found connections */
2818     PrintPinConnections (FP, true);
2819     PrintPadConnections (TOP_SIDE, FP, false);
2820     PrintPadConnections (BOTTOM_SIDE, FP, false);
2821     fputs ("\t}\n", FP);
2822     if (PrepareNextLoop (FP))
2823       return (true);
2824   }
2825   END_LOOP;
2826
2827   /* check all pads in element */
2828   PAD_LOOP (Element);
2829   {
2830     Cardinal layer;
2831     /* pad might have been checked before, add to list if not */
2832     if (TEST_FLAG (flag, pad))
2833       {
2834         PrintConnectionListEntry ((char *)EMPTY (pad->Name), NULL, true, FP);
2835         fputs ("\t\t__CHECKED_BEFORE__\n\t}\n", FP);
2836         continue;
2837       }
2838     layer = TEST_FLAG (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE;
2839     if (ADD_PAD_TO_LIST (layer, pad, flag))
2840       return true;
2841     DoIt (flag, true, AndDraw);
2842     /* print all found connections */
2843     PrintPadConnections (layer, FP, true);
2844     PrintPadConnections (layer ==
2845                          (TOP_SIDE ? BOTTOM_SIDE : TOP_SIDE),
2846                          FP, false);
2847     PrintPinConnections (FP, false);
2848     fputs ("\t}\n", FP);
2849     if (PrepareNextLoop (FP))
2850       return (true);
2851   }
2852   END_LOOP;
2853   fputs ("}\n\n", FP);
2854   return (false);
2855 }
2856
2857 /* ---------------------------------------------------------------------------
2858  * draws all new connections which have been found since the
2859  * routine was called the last time
2860  */
2861 static void
2862 DrawNewConnections (void)
2863 {
2864   int i;
2865   Cardinal position;
2866
2867   /* decrement 'i' to keep layerstack order */
2868   for (i = max_copper_layer - 1; i != -1; i--)
2869     {
2870       Cardinal layer = LayerStack[i];
2871
2872       if (PCB->Data->Layer[layer].On)
2873         {
2874           /* draw all new lines */
2875           position = LineList[layer].DrawLocation;
2876           for (; position < LineList[layer].Number; position++)
2877             DrawLine (LAYER_PTR (layer), LINELIST_ENTRY (layer, position));
2878           LineList[layer].DrawLocation = LineList[layer].Number;
2879
2880           /* draw all new arcs */
2881           position = ArcList[layer].DrawLocation;
2882           for (; position < ArcList[layer].Number; position++)
2883             DrawArc (LAYER_PTR (layer), ARCLIST_ENTRY (layer, position));
2884           ArcList[layer].DrawLocation = ArcList[layer].Number;
2885
2886           /* draw all new polygons */
2887           position = PolygonList[layer].DrawLocation;
2888           for (; position < PolygonList[layer].Number; position++)
2889             DrawPolygon (LAYER_PTR (layer), POLYGONLIST_ENTRY (layer, position));
2890           PolygonList[layer].DrawLocation = PolygonList[layer].Number;
2891         }
2892     }
2893
2894   /* draw all new pads */
2895   if (PCB->PinOn)
2896     for (i = 0; i < 2; i++)
2897       {
2898         position = PadList[i].DrawLocation;
2899
2900         for (; position < PadList[i].Number; position++)
2901           DrawPad (PADLIST_ENTRY (i, position));
2902         PadList[i].DrawLocation = PadList[i].Number;
2903       }
2904
2905   /* draw all new PVs; 'PVList' holds a list of pointers to the
2906    * sorted array pointers to PV data
2907    */
2908   while (PVList.DrawLocation < PVList.Number)
2909     {
2910       PinType *pv = PVLIST_ENTRY (PVList.DrawLocation);
2911
2912       if (TEST_FLAG (PINFLAG, pv))
2913         {
2914           if (PCB->PinOn)
2915             DrawPin (pv);
2916         }
2917       else if (PCB->ViaOn)
2918         DrawVia (pv);
2919       PVList.DrawLocation++;
2920     }
2921   /* draw the new rat-lines */
2922   if (PCB->RatOn)
2923     {
2924       position = RatList.DrawLocation;
2925       for (; position < RatList.Number; position++)
2926         DrawRat (RATLIST_ENTRY (position));
2927       RatList.DrawLocation = RatList.Number;
2928     }
2929 }
2930
2931 /* ---------------------------------------------------------------------------
2932  * find all connections to pins within one element
2933  */
2934 void
2935 LookupElementConnections (ElementType *Element, FILE * FP)
2936 {
2937   /* reset all currently marked connections */
2938   User = true;
2939   ClearFlagOnAllObjects (true, FOUNDFLAG);
2940   InitConnectionLookup ();
2941   PrintElementConnections (Element, FP, FOUNDFLAG, true);
2942   SetChangedFlag (true);
2943   if (Settings.RingBellWhenFinished)
2944     gui->beep ();
2945   FreeConnectionLookupMemory ();
2946   IncrementUndoSerialNumber ();
2947   User = false;
2948   Draw ();
2949 }
2950
2951 /* ---------------------------------------------------------------------------
2952  * find all connections to pins of all element
2953  */
2954 void
2955 LookupConnectionsToAllElements (FILE * FP)
2956 {
2957   /* reset all currently marked connections */
2958   User = false;
2959   ClearFlagOnAllObjects (false, FOUNDFLAG);
2960   InitConnectionLookup ();
2961
2962   ELEMENT_LOOP (PCB->Data);
2963   {
2964     /* break if abort dialog returned true */
2965     if (PrintElementConnections (element, FP, FOUNDFLAG, false))
2966       break;
2967     SEPARATE (FP);
2968     if (Settings.ResetAfterElement && n != 1)
2969       ClearFlagOnAllObjects (false, FOUNDFLAG);
2970   }
2971   END_LOOP;
2972   if (Settings.RingBellWhenFinished)
2973     gui->beep ();
2974   ClearFlagOnAllObjects (false, FOUNDFLAG);
2975   FreeConnectionLookupMemory ();
2976   Redraw ();
2977 }
2978
2979 /*---------------------------------------------------------------------------
2980  * add the starting object to the list of found objects
2981  */
2982 static bool
2983 ListStart (int type, void *ptr1, void *ptr2, void *ptr3, int flag)
2984 {
2985   DumpList ();
2986   switch (type)
2987     {
2988     case PIN_TYPE:
2989     case VIA_TYPE:
2990       {
2991         if (ADD_PV_TO_LIST ((PinType *) ptr2, flag))
2992           return true;
2993         break;
2994       }
2995
2996     case RATLINE_TYPE:
2997       {
2998         if (ADD_RAT_TO_LIST ((RatType *) ptr1, flag))
2999           return true;
3000         break;
3001       }
3002
3003     case LINE_TYPE:
3004       {
3005         int layer = GetLayerNumber (PCB->Data,
3006                                     (LayerType *) ptr1);
3007
3008         if (ADD_LINE_TO_LIST (layer, (LineType *) ptr2, flag))
3009           return true;
3010         break;
3011       }
3012
3013     case ARC_TYPE:
3014       {
3015         int layer = GetLayerNumber (PCB->Data,
3016                                     (LayerType *) ptr1);
3017
3018         if (ADD_ARC_TO_LIST (layer, (ArcType *) ptr2, flag))
3019           return true;
3020         break;
3021       }
3022
3023     case POLYGON_TYPE:
3024       {
3025         int layer = GetLayerNumber (PCB->Data,
3026                                     (LayerType *) ptr1);
3027
3028         if (ADD_POLYGON_TO_LIST (layer, (PolygonType *) ptr2, flag))
3029           return true;
3030         break;
3031       }
3032
3033     case PAD_TYPE:
3034       {
3035         PadType *pad = (PadType *) ptr2;
3036         if (ADD_PAD_TO_LIST
3037             (TEST_FLAG
3038              (ONSOLDERFLAG, pad) ? BOTTOM_SIDE : TOP_SIDE, pad, flag))
3039           return true;
3040         break;
3041       }
3042     }
3043   return (false);
3044 }
3045
3046
3047 /* ---------------------------------------------------------------------------
3048  * looks up all connections from the object at the given coordinates
3049  * the TheFlag (normally 'FOUNDFLAG') is set for all objects found
3050  * the objects are re-drawn if AndDraw is true
3051  * also the action is marked as undoable if AndDraw is true
3052  */
3053 void
3054 LookupConnection (Coord X, Coord Y, bool AndDraw, Coord Range, int flag,
3055                   bool AndRats)
3056 {
3057   void *ptr1, *ptr2, *ptr3;
3058   char *name;
3059   int type;
3060
3061   /* check if there are any pins or pads at that position */
3062
3063         reassign_no_drc_flags ();
3064
3065   type
3066     = SearchObjectByLocation (LOOKUP_FIRST, &ptr1, &ptr2, &ptr3, X, Y, Range);
3067   if (type == NO_TYPE)
3068     {
3069       type = SearchObjectByLocation (
3070         LOOKUP_MORE & ~(AndRats ? 0 : RATLINE_TYPE),
3071         &ptr1, &ptr2, &ptr3, X, Y, Range);
3072       if (type == NO_TYPE)
3073         return;
3074       if (type & SILK_TYPE)
3075         {
3076           int laynum = GetLayerNumber (PCB->Data,
3077                                        (LayerType *) ptr1);
3078
3079           /* don't mess with non-conducting objects! */
3080           if (laynum >= max_copper_layer || ((LayerType *)ptr1)->no_drc)
3081             return;
3082         }
3083     }
3084
3085   name = ConnectionName (type, ptr1, ptr2);
3086   hid_actionl ("NetlistShow", name, NULL);
3087
3088   User = AndDraw;
3089   InitConnectionLookup ();
3090
3091   /* now add the object to the appropriate list and start scanning
3092    * This is step (1) from the description
3093    */
3094   ListStart (type, ptr1, ptr2, ptr3, flag);
3095   DoIt (flag, AndRats, AndDraw);
3096   if (User)
3097     IncrementUndoSerialNumber ();
3098   User = false;
3099
3100   /* we are done */
3101   if (AndDraw)
3102     Draw ();
3103   if (AndDraw && Settings.RingBellWhenFinished)
3104     gui->beep ();
3105   FreeConnectionLookupMemory ();
3106 }
3107
3108 /* ---------------------------------------------------------------------------
3109  * find connections for rats nesting
3110  * assumes InitConnectionLookup() has already been done
3111  */
3112 void
3113 RatFindHook (int type, void *ptr1, void *ptr2, void *ptr3,
3114              bool undo, int flag, bool AndRats)
3115 {
3116   User = undo;
3117   DumpList ();
3118   ListStart (type, ptr1, ptr2, ptr3, flag);
3119   DoIt (flag, AndRats, false);
3120   User = false;
3121 }
3122
3123 /* ---------------------------------------------------------------------------
3124  * find all unused pins of all element
3125  */
3126 void
3127 LookupUnusedPins (FILE * FP)
3128 {
3129   /* reset all currently marked connections */
3130   User = true;
3131   ClearFlagOnAllObjects (true, FOUNDFLAG);
3132   InitConnectionLookup ();
3133
3134   ELEMENT_LOOP (PCB->Data);
3135   {
3136     /* break if abort dialog returned true;
3137      * passing NULL as filedescriptor discards the normal output
3138      */
3139     if (PrintAndSelectUnusedPinsAndPadsOfElement (element, FP, FOUNDFLAG))
3140       break;
3141   }
3142   END_LOOP;
3143
3144   if (Settings.RingBellWhenFinished)
3145     gui->beep ();
3146   FreeConnectionLookupMemory ();
3147   IncrementUndoSerialNumber ();
3148   User = false;
3149   Draw ();
3150 }
3151
3152 /* ---------------------------------------------------------------------------
3153  * resets all used flags of pins and vias
3154  */
3155 bool
3156 ClearFlagOnPinsViasAndPads (bool AndDraw, int flag)
3157 {
3158   bool change = false;
3159
3160   VIA_LOOP (PCB->Data);
3161   {
3162     if (TEST_FLAG (flag, via))
3163       {
3164         if (AndDraw)
3165           AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3166         CLEAR_FLAG (flag, via);
3167         if (AndDraw)
3168           DrawVia (via);
3169         change = true;
3170       }
3171   }
3172   END_LOOP;
3173   ELEMENT_LOOP (PCB->Data);
3174   {
3175     PIN_LOOP (element);
3176     {
3177       if (TEST_FLAG (flag, pin))
3178         {
3179           if (AndDraw)
3180             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3181           CLEAR_FLAG (flag, pin);
3182           if (AndDraw)
3183             DrawPin (pin);
3184           change = true;
3185         }
3186     }
3187     END_LOOP;
3188     PAD_LOOP (element);
3189     {
3190       if (TEST_FLAG (flag, pad))
3191         {
3192           if (AndDraw)
3193             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
3194           CLEAR_FLAG (flag, pad);
3195           if (AndDraw)
3196             DrawPad (pad);
3197           change = true;
3198         }
3199     }
3200     END_LOOP;
3201   }
3202   END_LOOP;
3203   if (change)
3204     SetChangedFlag (true);
3205   return change;
3206 }
3207
3208 /* ---------------------------------------------------------------------------
3209  * resets all used flags of LOs
3210  */
3211 bool
3212 ClearFlagOnLinesAndPolygons (bool AndDraw, int flag)
3213 {
3214   bool change = false;
3215
3216   RAT_LOOP (PCB->Data);
3217   {
3218     if (TEST_FLAG (flag, line))
3219       {
3220         if (AndDraw)
3221           AddObjectToFlagUndoList (RATLINE_TYPE, line, line, line);
3222         CLEAR_FLAG (flag, line);
3223         if (AndDraw)
3224           DrawRat (line);
3225         change = true;
3226       }
3227   }
3228   END_LOOP;
3229   COPPERLINE_LOOP (PCB->Data);
3230   {
3231     if (TEST_FLAG (flag, line))
3232       {
3233         if (AndDraw)
3234           AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3235         CLEAR_FLAG (flag, line);
3236         if (AndDraw)
3237           DrawLine (layer, line);
3238         change = true;
3239       }
3240   }
3241   ENDALL_LOOP;
3242   COPPERARC_LOOP (PCB->Data);
3243   {
3244     if (TEST_FLAG (flag, arc))
3245       {
3246         if (AndDraw)
3247           AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3248         CLEAR_FLAG (flag, arc);
3249         if (AndDraw)
3250           DrawArc (layer, arc);
3251         change = true;
3252       }
3253   }
3254   ENDALL_LOOP;
3255   COPPERPOLYGON_LOOP (PCB->Data);
3256   {
3257     if (TEST_FLAG (flag, polygon))
3258       {
3259         if (AndDraw)
3260           AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3261         CLEAR_FLAG (flag, polygon);
3262         if (AndDraw)
3263           DrawPolygon (layer, polygon);
3264         change = true;
3265       }
3266   }
3267   ENDALL_LOOP;
3268   if (change)
3269     SetChangedFlag (true);
3270   return change;
3271 }
3272
3273 /* ---------------------------------------------------------------------------
3274  * resets all found connections
3275  */
3276 bool
3277 ClearFlagOnAllObjects (bool AndDraw, int flag)
3278 {
3279   bool change = false;
3280
3281   change = ClearFlagOnPinsViasAndPads  (AndDraw, flag) || change;
3282   change = ClearFlagOnLinesAndPolygons (AndDraw, flag) || change;
3283
3284   return change;
3285 }
3286
3287 /*----------------------------------------------------------------------------
3288  * Dumps the list contents
3289  */
3290 static void
3291 DumpList (void)
3292 {
3293   Cardinal i;
3294
3295   for (i = 0; i < 2; i++)
3296     {
3297       PadList[i].Number = 0;
3298       PadList[i].Location = 0;
3299       PadList[i].DrawLocation = 0;
3300     }
3301
3302   PVList.Number = 0;
3303   PVList.Location = 0;
3304
3305   for (i = 0; i < max_copper_layer; i++)
3306     {
3307       LineList[i].Location = 0;
3308       LineList[i].DrawLocation = 0;
3309       LineList[i].Number = 0;
3310       ArcList[i].Location = 0;
3311       ArcList[i].DrawLocation = 0;
3312       ArcList[i].Number = 0;
3313       PolygonList[i].Location = 0;
3314       PolygonList[i].DrawLocation = 0;
3315       PolygonList[i].Number = 0;
3316     }
3317   RatList.Number = 0;
3318   RatList.Location = 0;
3319   RatList.DrawLocation = 0;
3320 }
3321
3322 struct drc_info
3323 {
3324   int flag;
3325 };
3326
3327 /*-----------------------------------------------------------------------------
3328  * Check for DRC violations on a single net starting from the pad or pin
3329  * sees if the connectivity changes when everything is bloated, or shrunk
3330  */
3331 static bool
3332 DRCFind (int What, void *ptr1, void *ptr2, void *ptr3)
3333 {
3334   Coord x, y;
3335   int object_count;
3336   long int *object_id_list;
3337   int *object_type_list;
3338   DrcViolationType *violation;
3339   int flag;
3340
3341   if (PCB->Shrink != 0)
3342     {
3343       Bloat = -PCB->Shrink;
3344       ListStart (What, ptr1, ptr2, ptr3, DRCFLAG | SELECTEDFLAG);
3345       DoIt (DRCFLAG | SELECTEDFLAG, true, false);
3346       /* ok now the shrunk net has the SELECTEDFLAG set */
3347       DumpList ();
3348       ListStart (What, ptr1, ptr2, ptr3, FOUNDFLAG);
3349       Bloat = 0;
3350       drc = true;               /* abort the search if we find anything not already found */
3351       if (DoIt (FOUNDFLAG, true, false))
3352         {
3353           DumpList ();
3354           /* make the flag changes undoable */
3355           ClearFlagOnAllObjects (false, FOUNDFLAG | SELECTEDFLAG);
3356           User = true;
3357           drc = false;
3358           Bloat = -PCB->Shrink;
3359           ListStart (What, ptr1, ptr2, ptr3, SELECTEDFLAG);
3360           DoIt (SELECTEDFLAG, true, true);
3361           DumpList ();
3362           ListStart (What, ptr1, ptr2, ptr3, FOUNDFLAG);
3363           Bloat = 0;
3364           drc = true;
3365           DoIt (FOUNDFLAG, true, true);
3366           DumpList ();
3367           User = false;
3368           drc = false;
3369           drcerr_count++;
3370           LocateError (&x, &y);
3371           BuildObjectList (&object_count, &object_id_list, &object_type_list);
3372           violation = pcb_drc_violation_new (_("Potential for broken trace"),
3373                                              _("Insufficient overlap between objects can lead to broken tracks\n"
3374                                                "due to registration errors with old wheel style photo-plotters."),
3375                                              x, y,
3376                                              0,     /* ANGLE OF ERROR UNKNOWN */
3377                                              FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3378                                              0,     /* MAGNITUDE OF ERROR UNKNOWN */
3379                                              PCB->Shrink,
3380                                              object_count,
3381                                              object_id_list,
3382                                              object_type_list);
3383           append_drc_violation (violation);
3384           pcb_drc_violation_free (violation);
3385           free (object_id_list);
3386           free (object_type_list);
3387
3388           if (!throw_drc_dialog())
3389             return (true);
3390           IncrementUndoSerialNumber ();
3391           Undo (true);
3392         }
3393       DumpList ();
3394     }
3395   /* now check the bloated condition */
3396   drc = false;
3397   ClearFlagOnAllObjects (false, FOUNDFLAG | SELECTEDFLAG);
3398   Bloat = 0;
3399   ListStart (What, ptr1, ptr2, ptr3, SELECTEDFLAG);
3400   DoIt (SELECTEDFLAG, true, false);
3401   DumpList ();
3402   flag = FOUNDFLAG;
3403   ListStart (What, ptr1, ptr2, ptr3, flag);
3404   Bloat = PCB->Bloat;
3405   drc = true;
3406   while (DoIt (flag, true, false))
3407     {
3408       DumpList ();
3409       /* make the flag changes undoable */
3410       ClearFlagOnAllObjects (false, FOUNDFLAG | SELECTEDFLAG);
3411       User = true;
3412       drc = false;
3413       Bloat = 0;
3414       ListStart (What, ptr1, ptr2, ptr3, SELECTEDFLAG);
3415       DoIt (SELECTEDFLAG, true, true);
3416       DumpList ();
3417       ListStart (What, ptr1, ptr2, ptr3, FOUNDFLAG);
3418       Bloat = PCB->Bloat;
3419       drc = true;
3420       DoIt (FOUNDFLAG, true, true);
3421       DumpList ();
3422       drcerr_count++;
3423       LocateError (&x, &y);
3424       BuildObjectList (&object_count, &object_id_list, &object_type_list);
3425       violation = pcb_drc_violation_new (_("Copper areas too close"),
3426                                          _("Circuits that are too close may bridge during imaging, etching,\n"
3427                                            "plating, or soldering processes resulting in a direct short."),
3428                                          x, y,
3429                                          0,     /* ANGLE OF ERROR UNKNOWN */
3430                                          FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3431                                          0,     /* MAGNITUDE OF ERROR UNKNOWN */
3432                                          PCB->Bloat,
3433                                          object_count,
3434                                          object_id_list,
3435                                          object_type_list);
3436       append_drc_violation (violation);
3437       pcb_drc_violation_free (violation);
3438       free (object_id_list);
3439       free (object_type_list);
3440       User = false;
3441       drc = false;
3442       if (!throw_drc_dialog())
3443         return (true);
3444       IncrementUndoSerialNumber ();
3445       Undo (true);
3446       /* highlight the rest of the encroaching net so it's not reported again */
3447       flag = FOUNDFLAG | SELECTEDFLAG;
3448       Bloat = 0;
3449       ListStart (thing_type, thing_ptr1, thing_ptr2, thing_ptr3, flag);
3450       DoIt (flag, true, true);
3451       DumpList ();
3452       drc = true;
3453       Bloat = PCB->Bloat;
3454       ListStart (What, ptr1, ptr2, ptr3, flag);
3455     }
3456   drc = false;
3457   DumpList ();
3458   ClearFlagOnAllObjects (false, FOUNDFLAG | SELECTEDFLAG);
3459   return (false);
3460 }
3461
3462 /* DRC clearance callback */
3463
3464 static int
3465 drc_callback (DataType *data, LayerType *layer, PolygonType *polygon,
3466               int type, void *ptr1, void *ptr2, void *userdata)
3467 {
3468   struct drc_info *i = (struct drc_info *) userdata;
3469   char *message;
3470   Coord x, y;
3471   int object_count;
3472   long int *object_id_list;
3473   int *object_type_list;
3474   DrcViolationType *violation;
3475
3476   LineType *line = (LineType *) ptr2;
3477   ArcType *arc = (ArcType *) ptr2;
3478   PinType *pin = (PinType *) ptr2;
3479   PadType *pad = (PadType *) ptr2;
3480
3481   SetThing (type, ptr1, ptr2, ptr2);
3482
3483   switch (type)
3484     {
3485     case LINE_TYPE:
3486       if (line->Clearance < 2 * PCB->Bloat)
3487         {
3488           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3489           SET_FLAG (i->flag, line);
3490           message = _("Line with insufficient clearance inside polygon\n");
3491           goto doIsBad;
3492         }
3493       break;
3494     case ARC_TYPE:
3495       if (arc->Clearance < 2 * PCB->Bloat)
3496         {
3497           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3498           SET_FLAG (i->flag, arc);
3499           message = _("Arc with insufficient clearance inside polygon\n");
3500           goto doIsBad;
3501         }
3502       break;
3503     case PAD_TYPE:
3504       if (pad->Clearance && pad->Clearance < 2 * PCB->Bloat)
3505         if (IsPadInPolygon(pad,polygon))
3506           {
3507             AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3508             SET_FLAG (i->flag, pad);
3509             message = _("Pad with insufficient clearance inside polygon\n");
3510             goto doIsBad;
3511           }
3512       break;
3513     case PIN_TYPE:
3514       if (pin->Clearance && pin->Clearance < 2 * PCB->Bloat)
3515         {
3516           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3517           SET_FLAG (i->flag, pin);
3518           message = _("Pin with insufficient clearance inside polygon\n");
3519           goto doIsBad;
3520         }
3521       break;
3522     case VIA_TYPE:
3523       if (pin->Clearance && pin->Clearance < 2 * PCB->Bloat)
3524         {
3525           AddObjectToFlagUndoList (type, ptr1, ptr2, ptr2);
3526           SET_FLAG (i->flag, pin);
3527           message = _("Via with insufficient clearance inside polygon\n");
3528           goto doIsBad;
3529         }
3530       break;
3531     default:
3532       Message ("hace: Bad Plow object in callback\n");
3533     }
3534   return 0;
3535
3536 doIsBad:
3537   AddObjectToFlagUndoList (POLYGON_TYPE, layer, polygon, polygon);
3538   SET_FLAG (FOUNDFLAG, polygon);
3539   DrawPolygon (layer, polygon);
3540   DrawObject (type, ptr1, ptr2);
3541   drcerr_count++;
3542   LocateError (&x, &y);
3543   BuildObjectList (&object_count, &object_id_list, &object_type_list);
3544   violation = pcb_drc_violation_new (message,
3545                                      _("Circuits that are too close may bridge during imaging, etching,\n"
3546                                        "plating, or soldering processes resulting in a direct short."),
3547                                      x, y,
3548                                      0,     /* ANGLE OF ERROR UNKNOWN */
3549                                      FALSE, /* MEASUREMENT OF ERROR UNKNOWN */
3550                                      0,     /* MAGNITUDE OF ERROR UNKNOWN */
3551                                      PCB->Bloat,
3552                                      object_count,
3553                                      object_id_list,
3554                                      object_type_list);
3555   append_drc_violation (violation);
3556   pcb_drc_violation_free (violation);
3557   free (object_id_list);
3558   free (object_type_list);
3559
3560   if (!throw_drc_dialog())
3561     return 1;
3562
3563   IncrementUndoSerialNumber ();
3564   Undo (true);
3565   return 0;
3566 }
3567
3568 /*-----------------------------------------------------------------------------
3569  * Check for DRC violations
3570  * see if the connectivity changes when everything is bloated, or shrunk
3571  */
3572 int
3573 DRCAll (void)
3574 {
3575   Coord x, y;
3576   int object_count;
3577   long int *object_id_list;
3578   int *object_type_list;
3579   DrcViolationType *violation;
3580   int tmpcnt;
3581   int nopastecnt = 0;
3582   bool IsBad;
3583   struct drc_info info;
3584
3585   reset_drc_dialog_message();
3586
3587   IsBad = false;
3588   drcerr_count = 0;
3589   SaveStackAndVisibility ();
3590   ResetStackAndVisibility ();
3591   hid_action ("LayersChanged");
3592   InitConnectionLookup ();
3593
3594   if (ClearFlagOnAllObjects (true, FOUNDFLAG | DRCFLAG | SELECTEDFLAG))
3595     {
3596       IncrementUndoSerialNumber ();
3597       Draw ();
3598     }
3599
3600   User = false;
3601
3602   ELEMENT_LOOP (PCB->Data);
3603   {
3604     PIN_LOOP (element);
3605     {
3606       if (!TEST_FLAG (DRCFLAG, pin)
3607           && DRCFind (PIN_TYPE, (void *) element, (void *) pin, (void *) pin))
3608         {
3609           IsBad = true;
3610           break;
3611         }
3612     }
3613     END_LOOP;
3614     if (IsBad)
3615       break;
3616     PAD_LOOP (element);
3617     {
3618
3619       /* count up how many pads have no solderpaste openings */
3620       if (TEST_FLAG (NOPASTEFLAG, pad))
3621         nopastecnt++;
3622
3623       if (!TEST_FLAG (DRCFLAG, pad)
3624           && DRCFind (PAD_TYPE, (void *) element, (void *) pad, (void *) pad))
3625         {
3626           IsBad = true;
3627           break;
3628         }
3629     }
3630     END_LOOP;
3631     if (IsBad)
3632       break;
3633   }
3634   END_LOOP;
3635   if (!IsBad)
3636     VIA_LOOP (PCB->Data);
3637   {
3638     if (!TEST_FLAG (DRCFLAG, via)
3639         && DRCFind (VIA_TYPE, (void *) via, (void *) via, (void *) via))
3640       {
3641         IsBad = true;
3642         break;
3643       }
3644   }
3645   END_LOOP;
3646
3647   ClearFlagOnAllObjects (false, IsBad ? DRCFLAG : (FOUNDFLAG | DRCFLAG | SELECTEDFLAG));
3648   info.flag = SELECTEDFLAG;
3649   /* check minimum widths and polygon clearances */
3650   if (!IsBad)
3651     {
3652       COPPERLINE_LOOP (PCB->Data);
3653       {
3654         /* check line clearances in polygons */
3655         if (PlowsPolygon (PCB->Data, LINE_TYPE, layer, line, drc_callback, &info))
3656           {
3657             IsBad = true;
3658             break;
3659           }
3660         if (line->Thickness < PCB->minWid)
3661           {
3662             AddObjectToFlagUndoList (LINE_TYPE, layer, line, line);
3663             SET_FLAG (SELECTEDFLAG, line);
3664             DrawLine (layer, line);
3665             drcerr_count++;
3666             SetThing (LINE_TYPE, layer, line, line);
3667             LocateError (&x, &y);
3668             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3669             violation = pcb_drc_violation_new (_("Line width is too thin"),
3670                                                _("Process specifications dictate a minimum feature-width\n"
3671                                                  "that can reliably be reproduced"),
3672                                                x, y,
3673                                                0,    /* ANGLE OF ERROR UNKNOWN */
3674                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3675                                                line->Thickness,
3676                                                PCB->minWid,
3677                                                object_count,
3678                                                object_id_list,
3679                                                object_type_list);
3680             append_drc_violation (violation);
3681             pcb_drc_violation_free (violation);
3682             free (object_id_list);
3683             free (object_type_list);
3684             if (!throw_drc_dialog())
3685               {
3686                 IsBad = true;
3687                 break;
3688               }
3689             IncrementUndoSerialNumber ();
3690             Undo (false);
3691           }
3692       }
3693       ENDALL_LOOP;
3694     }
3695   if (!IsBad)
3696     {
3697       COPPERARC_LOOP (PCB->Data);
3698       {
3699         if (PlowsPolygon (PCB->Data, ARC_TYPE, layer, arc, drc_callback, &info))
3700           {
3701             IsBad = true;
3702             break;
3703           }
3704         if (arc->Thickness < PCB->minWid)
3705           {
3706             AddObjectToFlagUndoList (ARC_TYPE, layer, arc, arc);
3707             SET_FLAG (SELECTEDFLAG, arc);
3708             DrawArc (layer, arc);
3709             drcerr_count++;
3710             SetThing (ARC_TYPE, layer, arc, arc);
3711             LocateError (&x, &y);
3712             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3713             violation = pcb_drc_violation_new (_("Arc width is too thin"),
3714                                                _("Process specifications dictate a minimum feature-width\n"
3715                                                  "that can reliably be reproduced"),
3716                                                x, y,
3717                                                0,    /* ANGLE OF ERROR UNKNOWN */
3718                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3719                                                arc->Thickness,
3720                                                PCB->minWid,
3721                                                object_count,
3722                                                object_id_list,
3723                                                object_type_list);
3724             append_drc_violation (violation);
3725             pcb_drc_violation_free (violation);
3726             free (object_id_list);
3727             free (object_type_list);
3728             if (!throw_drc_dialog())
3729               {
3730                 IsBad = true;
3731                 break;
3732               }
3733             IncrementUndoSerialNumber ();
3734             Undo (false);
3735           }
3736       }
3737       ENDALL_LOOP;
3738     }
3739   if (!IsBad)
3740     {
3741       ALLPIN_LOOP (PCB->Data);
3742       {
3743         if (PlowsPolygon (PCB->Data, PIN_TYPE, element, pin, drc_callback, &info))
3744           {
3745             IsBad = true;
3746             break;
3747           }
3748         if (!TEST_FLAG (HOLEFLAG, pin) &&
3749             pin->Thickness - pin->DrillingHole < 2 * PCB->minRing)
3750           {
3751             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3752             SET_FLAG (SELECTEDFLAG, pin);
3753             DrawPin (pin);
3754             drcerr_count++;
3755             SetThing (PIN_TYPE, element, pin, pin);
3756             LocateError (&x, &y);
3757             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3758             violation = pcb_drc_violation_new (_("Pin annular ring too small"),
3759                                                _("Annular rings that are too small may erode during etching,\n"
3760                                                  "resulting in a broken connection"),
3761                                                x, y,
3762                                                0,    /* ANGLE OF ERROR UNKNOWN */
3763                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3764                                                (pin->Thickness - pin->DrillingHole) / 2,
3765                                                PCB->minRing,
3766                                                object_count,
3767                                                object_id_list,
3768                                                object_type_list);
3769             append_drc_violation (violation);
3770             pcb_drc_violation_free (violation);
3771             free (object_id_list);
3772             free (object_type_list);
3773             if (!throw_drc_dialog())
3774               {
3775                 IsBad = true;
3776                 break;
3777               }
3778             IncrementUndoSerialNumber ();
3779             Undo (false);
3780           }
3781         if (pin->DrillingHole < PCB->minDrill)
3782           {
3783             AddObjectToFlagUndoList (PIN_TYPE, element, pin, pin);
3784             SET_FLAG (SELECTEDFLAG, pin);
3785             DrawPin (pin);
3786             drcerr_count++;
3787             SetThing (PIN_TYPE, element, pin, pin);
3788             LocateError (&x, &y);
3789             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3790             violation = pcb_drc_violation_new (_("Pin drill size is too small"),
3791                                                _("Process rules dictate the minimum drill size which can be used"),
3792                                                x, y,
3793                                                0,    /* ANGLE OF ERROR UNKNOWN */
3794                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3795                                                pin->DrillingHole,
3796                                                PCB->minDrill,
3797                                                object_count,
3798                                                object_id_list,
3799                                                object_type_list);
3800             append_drc_violation (violation);
3801             pcb_drc_violation_free (violation);
3802             free (object_id_list);
3803             free (object_type_list);
3804             if (!throw_drc_dialog())
3805               {
3806                 IsBad = true;
3807                 break;
3808               }
3809             IncrementUndoSerialNumber ();
3810             Undo (false);
3811           }
3812       }
3813       ENDALL_LOOP;
3814     }
3815   if (!IsBad)
3816     {
3817       ALLPAD_LOOP (PCB->Data);
3818       {
3819         if (PlowsPolygon (PCB->Data, PAD_TYPE, element, pad, drc_callback, &info))
3820           {
3821             IsBad = true;
3822             break;
3823           }
3824         if (pad->Thickness < PCB->minWid)
3825           {
3826             AddObjectToFlagUndoList (PAD_TYPE, element, pad, pad);
3827             SET_FLAG (SELECTEDFLAG, pad);
3828             DrawPad (pad);
3829             drcerr_count++;
3830             SetThing (PAD_TYPE, element, pad, pad);
3831             LocateError (&x, &y);
3832             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3833             violation = pcb_drc_violation_new (_("Pad is too thin"),
3834                                                _("Pads which are too thin may erode during etching,\n"
3835                                                   "resulting in a broken or unreliable connection"),
3836                                                x, y,
3837                                                0,    /* ANGLE OF ERROR UNKNOWN */
3838                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3839                                                pad->Thickness,
3840                                                PCB->minWid,
3841                                                object_count,
3842                                                object_id_list,
3843                                                object_type_list);
3844             append_drc_violation (violation);
3845             pcb_drc_violation_free (violation);
3846             free (object_id_list);
3847             free (object_type_list);
3848             if (!throw_drc_dialog())
3849               {
3850                 IsBad = true;
3851                 break;
3852               }
3853             IncrementUndoSerialNumber ();
3854             Undo (false);
3855           }
3856       }
3857       ENDALL_LOOP;
3858     }
3859   if (!IsBad)
3860     {
3861       VIA_LOOP (PCB->Data);
3862       {
3863         if (PlowsPolygon (PCB->Data, VIA_TYPE, via, via, drc_callback, &info))
3864           {
3865             IsBad = true;
3866             break;
3867           }
3868         if (!TEST_FLAG (HOLEFLAG, via) &&
3869             via->Thickness - via->DrillingHole < 2 * PCB->minRing)
3870           {
3871             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3872             SET_FLAG (SELECTEDFLAG, via);
3873             DrawVia (via);
3874             drcerr_count++;
3875             SetThing (VIA_TYPE, via, via, via);
3876             LocateError (&x, &y);
3877             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3878             violation = pcb_drc_violation_new (_("Via annular ring too small"),
3879                                                _("Annular rings that are too small may erode during etching,\n"
3880                                                  "resulting in a broken connection"),
3881                                                x, y,
3882                                                0,    /* ANGLE OF ERROR UNKNOWN */
3883                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3884                                                (via->Thickness - via->DrillingHole) / 2,
3885                                                PCB->minRing,
3886                                                object_count,
3887                                                object_id_list,
3888                                                object_type_list);
3889             append_drc_violation (violation);
3890             pcb_drc_violation_free (violation);
3891             free (object_id_list);
3892             free (object_type_list);
3893             if (!throw_drc_dialog())
3894               {
3895                 IsBad = true;
3896                 break;
3897               }
3898             IncrementUndoSerialNumber ();
3899             Undo (false);
3900           }
3901         if (via->DrillingHole < PCB->minDrill)
3902           {
3903             AddObjectToFlagUndoList (VIA_TYPE, via, via, via);
3904             SET_FLAG (SELECTEDFLAG, via);
3905             DrawVia (via);
3906             drcerr_count++;
3907             SetThing (VIA_TYPE, via, via, via);
3908             LocateError (&x, &y);
3909             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3910             violation = pcb_drc_violation_new (_("Via drill size is too small"),
3911                                                _("Process rules dictate the minimum drill size which can be used"),
3912                                                x, y,
3913                                                0,    /* ANGLE OF ERROR UNKNOWN */
3914                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3915                                                via->DrillingHole,
3916                                                PCB->minDrill,
3917                                                object_count,
3918                                                object_id_list,
3919                                                object_type_list);
3920             append_drc_violation (violation);
3921             pcb_drc_violation_free (violation);
3922             free (object_id_list);
3923             free (object_type_list);
3924             if (!throw_drc_dialog())
3925               {
3926                 IsBad = true;
3927                 break;
3928               }
3929             IncrementUndoSerialNumber ();
3930             Undo (false);
3931           }
3932       }
3933       END_LOOP;
3934     }
3935
3936   FreeConnectionLookupMemory ();
3937   Bloat = 0;
3938
3939   /* check silkscreen minimum widths outside of elements */
3940   /* XXX - need to check text and polygons too! */
3941   if (!IsBad)
3942     {
3943       SILKLINE_LOOP (PCB->Data);
3944       {
3945         if (line->Thickness < PCB->minSlk)
3946           {
3947             SET_FLAG (SELECTEDFLAG, line);
3948             DrawLine (layer, line);
3949             drcerr_count++;
3950             SetThing (LINE_TYPE, layer, line, line);
3951             LocateError (&x, &y);
3952             BuildObjectList (&object_count, &object_id_list, &object_type_list);
3953             violation = pcb_drc_violation_new (_("Silk line is too thin"),
3954                                                _("Process specifications dictate a minimum silkscreen feature-width\n"
3955                                                  "that can reliably be reproduced"),
3956                                                x, y,
3957                                                0,    /* ANGLE OF ERROR UNKNOWN */
3958                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
3959                                                line->Thickness,
3960                                                PCB->minSlk,
3961                                                object_count,
3962                                                object_id_list,
3963                                                object_type_list);
3964             append_drc_violation (violation);
3965             pcb_drc_violation_free (violation);
3966             free (object_id_list);
3967             free (object_type_list);
3968             if (!throw_drc_dialog())
3969               {
3970                 IsBad = true;
3971                 break;
3972               }
3973           }
3974       }
3975       ENDALL_LOOP;
3976     }
3977
3978   /* check silkscreen minimum widths inside of elements */
3979   /* XXX - need to check text and polygons too! */
3980   if (!IsBad)
3981     {
3982       ELEMENT_LOOP (PCB->Data);
3983       {
3984         tmpcnt = 0;
3985         ELEMENTLINE_LOOP (element);
3986         {
3987           if (line->Thickness < PCB->minSlk)
3988             tmpcnt++;
3989         }
3990         END_LOOP;
3991         if (tmpcnt > 0)
3992           {
3993             char *title;
3994             char *name;
3995             char *buffer;
3996             int buflen;
3997
3998             SET_FLAG (SELECTEDFLAG, element);
3999             DrawElement (element);
4000             drcerr_count++;
4001             SetThing (ELEMENT_TYPE, element, element, element);
4002             LocateError (&x, &y);
4003             BuildObjectList (&object_count, &object_id_list, &object_type_list);
4004
4005             title = _("Element %s has %i silk lines which are too thin");
4006             name = (char *)UNKNOWN (NAMEONPCB_NAME (element));
4007
4008             /* -4 is for the %s and %i place-holders */
4009             /* +11 is the max printed length for a 32 bit integer */
4010             /* +1 is for the \0 termination */
4011             buflen = strlen (title) - 4 + strlen (name) + 11 + 1;
4012             buffer = (char *)malloc (buflen);
4013             snprintf (buffer, buflen, title, name, tmpcnt);
4014
4015             violation = pcb_drc_violation_new (buffer,
4016                                                _("Process specifications dictate a minimum silkscreen\n"
4017                                                "feature-width that can reliably be reproduced"),
4018                                                x, y,
4019                                                0,    /* ANGLE OF ERROR UNKNOWN */
4020                                                TRUE, /* MEASUREMENT OF ERROR KNOWN */
4021                                                0,    /* MINIMUM OFFENDING WIDTH UNKNOWN */
4022                                                PCB->minSlk,
4023                                                object_count,
4024                                                object_id_list,
4025                                                object_type_list);
4026             free (buffer);
4027             append_drc_violation (violation);
4028             pcb_drc_violation_free (violation);
4029             free (object_id_list);
4030             free (object_type_list);
4031             if (!throw_drc_dialog())
4032               {
4033                 IsBad = true;
4034                 break;
4035               }
4036           }
4037       }
4038       END_LOOP;
4039     }
4040
4041
4042   if (IsBad)
4043     {
4044       IncrementUndoSerialNumber ();
4045     }
4046
4047
4048   RestoreStackAndVisibility ();
4049   hid_action ("LayersChanged");
4050   gui->invalidate_all ();
4051
4052   if (nopastecnt > 0)
4053     {
4054       Message (ngettext ("Warning: %d pad has the nopaste flag set.\n",
4055                          "Warning: %d pads have the nopaste flag set.\n",
4056                          nopastecnt), nopastecnt);
4057     }
4058   return IsBad ? -drcerr_count : drcerr_count;
4059 }
4060
4061 /*----------------------------------------------------------------------------
4062  * Locate the coordinatates of offending item (thing)
4063  */
4064 static void
4065 LocateError (Coord *x, Coord *y)
4066 {
4067   switch (thing_type)
4068     {
4069     case LINE_TYPE:
4070       {
4071         LineType *line = (LineType *) thing_ptr3;
4072         *x = (line->Point1.X + line->Point2.X) / 2;
4073         *y = (line->Point1.Y + line->Point2.Y) / 2;
4074         break;
4075       }
4076     case ARC_TYPE:
4077       {
4078         ArcType *arc = (ArcType *) thing_ptr3;
4079         *x = arc->X;
4080         *y = arc->Y;
4081         break;
4082       }
4083     case POLYGON_TYPE:
4084       {
4085         PolygonType *polygon = (PolygonType *) thing_ptr3;
4086         *x =
4087           (polygon->Clipped->contours->xmin +
4088            polygon->Clipped->contours->xmax) / 2;
4089         *y =
4090           (polygon->Clipped->contours->ymin +
4091            polygon->Clipped->contours->ymax) / 2;
4092         break;
4093       }
4094     case PIN_TYPE:
4095     case VIA_TYPE:
4096       {
4097         PinType *pin = (PinType *) thing_ptr3;
4098         *x = pin->X;
4099         *y = pin->Y;
4100         break;
4101       }
4102     case PAD_TYPE:
4103       {
4104         PadType *pad = (PadType *) thing_ptr3;
4105         *x = (pad->Point1.X + pad->Point2.X) / 2;
4106         *y = (pad->Point1.Y + pad->Point2.Y) / 2;
4107         break;
4108       }
4109     case ELEMENT_TYPE:
4110       {
4111         ElementType *element = (ElementType *) thing_ptr3;
4112         *x = element->MarkX;
4113         *y = element->MarkY;
4114         break;
4115       }
4116     default:
4117       return;
4118     }
4119 }
4120
4121
4122 /*----------------------------------------------------------------------------
4123  * Build a list of the of offending items by ID. (Currently just "thing")
4124  */
4125 static void
4126 BuildObjectList (int *object_count, long int **object_id_list, int **object_type_list)
4127 {
4128   *object_count = 0;
4129   *object_id_list = NULL;
4130   *object_type_list = NULL;
4131
4132   switch (thing_type)
4133     {
4134     case LINE_TYPE:
4135     case ARC_TYPE:
4136     case POLYGON_TYPE:
4137     case PIN_TYPE:
4138     case VIA_TYPE:
4139     case PAD_TYPE:
4140     case ELEMENT_TYPE:
4141     case RATLINE_TYPE:
4142       *object_count = 1;
4143       *object_id_list = (long int *)malloc (sizeof (long int));
4144       *object_type_list = (int *)malloc (sizeof (int));
4145       **object_id_list = ((AnyObjectType *)thing_ptr3)->ID;
4146       **object_type_list = thing_type;
4147       return;
4148
4149     default:
4150       fprintf (stderr,
4151                _("Internal error in BuildObjectList: unknown object type %i\n"),
4152                thing_type);
4153     }
4154 }
4155
4156
4157 /*----------------------------------------------------------------------------
4158  * center the display to show the offending item (thing)
4159  */
4160 static void
4161 GotoError (void)
4162 {
4163   Coord X, Y;
4164
4165   LocateError (&X, &Y);
4166
4167   switch (thing_type)
4168     {
4169     case LINE_TYPE:
4170     case ARC_TYPE:
4171     case POLYGON_TYPE:
4172       ChangeGroupVisibility (
4173           GetLayerNumber (PCB->Data, (LayerType *) thing_ptr1),
4174           true, true);
4175     }
4176   CenterDisplay (X, Y);
4177 }
4178
4179 void
4180 InitConnectionLookup (void)
4181 {
4182   InitComponentLookup ();
4183   InitLayoutLookup ();
4184 }
4185
4186 void
4187 FreeConnectionLookupMemory (void)
4188 {
4189   FreeComponentLookupMemory ();
4190   FreeLayoutLookupMemory ();
4191 }