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