1 /*
2  * This program source code file is part of KICAD, a free EDA CAD application.
3  *
4  * Copyright (C) 2013-2017 CERN
5  * Copyright (C) 2018-2020 KiCad Developers, see AUTHORS.txt for contributors.
6  * @author Maciej Suminski <maciej.suminski@cern.ch>
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, you may find one here:
21  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22  * or you may search the http://www.gnu.org website for the version 2 license,
23  * or you may write to the Free Software Foundation, Inc.,
24  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
25  */
26 
27 #ifndef __CONNECTIVITY_DATA_H
28 #define __CONNECTIVITY_DATA_H
29 
30 #include <core/typeinfo.h>
31 #include <core/spinlock.h>
32 
33 #include <memory>
34 #include <mutex>
35 #include <vector>
36 #include <wx/string.h>
37 
38 #include <math/vector2d.h>
39 #include <geometry/shape_poly_set.h>
40 #include <zone.h>
41 
42 class FROM_TO_CACHE;
43 class CN_CLUSTER;
44 class CN_CONNECTIVITY_ALGO;
45 class CN_EDGE;
46 class BOARD;
47 class BOARD_COMMIT;
48 class BOARD_CONNECTED_ITEM;
49 class BOARD_ITEM;
50 class ZONE;
51 class RN_DATA;
52 class RN_NET;
53 class PCB_TRACK;
54 class PAD;
55 class FOOTPRINT;
56 class PROGRESS_REPORTER;
57 
58 
59 struct CN_DISJOINT_NET_ENTRY
60 {
61     int net;
62     BOARD_CONNECTED_ITEM *a, *b;
63     VECTOR2I anchorA, anchorB;
64 };
65 
66 
67 /**
68  * A structure used for calculating isolated islands on a given zone across all its layers
69  */
70 struct CN_ZONE_ISOLATED_ISLAND_LIST
71 {
CN_ZONE_ISOLATED_ISLAND_LISTCN_ZONE_ISOLATED_ISLAND_LIST72     CN_ZONE_ISOLATED_ISLAND_LIST( ZONE* aZone ) :
73             m_zone( aZone )
74     {}
75 
76     ZONE* m_zone;
77 
78     std::map<PCB_LAYER_ID, std::vector<int>> m_islands;
79 };
80 
81 
82 struct RN_DYNAMIC_LINE
83 {
84     int netCode;
85     VECTOR2I a, b;
86 };
87 
88 
89 /**
90  * Controls how nets are propagated through clusters
91  */
92 enum class PROPAGATE_MODE
93 {
94     SKIP_CONFLICTS,     /// Clusters with conflicting drivers are not updated (default)
95     RESOLVE_CONFLICTS   /// Clusters with conflicting drivers are updated to the most popular net
96 };
97 
98 
99 // a wrapper class encompassing the connectivity computation algorithm and the
100 class CONNECTIVITY_DATA
101 {
102 public:
103     CONNECTIVITY_DATA();
104     ~CONNECTIVITY_DATA();
105 
106     CONNECTIVITY_DATA( const std::vector<BOARD_ITEM*>& aItems, bool aSkipItems = false );
107 
108     /**
109      * Function Build()
110      * Builds the connectivity database for the board aBoard.
111      */
112     void Build( BOARD* aBoard, PROGRESS_REPORTER* aReporter = nullptr );
113 
114     /**
115      * Function Build()
116      * Builds the connectivity database for a set of items aItems.
117      */
118     void Build( const std::vector<BOARD_ITEM*>& aItems );
119 
120     /**
121      * Function Add()
122      * Adds an item to the connectivity data.
123      * @param aItem is an item to be added.
124      * @return True if operation succeeded.
125      */
126     bool Add( BOARD_ITEM* aItem );
127 
128     /**
129      * Function Remove()
130      * Removes an item from the connectivity data.
131      * @param aItem is an item to be updated.
132      * @return True if operation succeeded.
133      */
134     bool Remove( BOARD_ITEM* aItem );
135 
136     /**
137      * Function Update()
138      * Updates the connectivity data for an item.
139      * @param aItem is an item to be updated.
140      * @return True if operation succeeded.
141      */
142     bool Update( BOARD_ITEM* aItem );
143 
144     /**
145      * Moves the connectivity list anchors.  N.B., this does not move the bounding
146      * boxes for the RTree, so the use of this function will invalidate the
147      * connectivity data for uses other than the dynamic ratsnest
148      *
149      * @param aDelta vector for movement of the tree
150      */
151     void Move( const VECTOR2I& aDelta );
152 
153     /**
154      * Function Clear()
155      * Erases the connectivity database.
156      */
157     void Clear();
158 
159     /**
160      * Function GetNetCount()
161      * Returns the total number of nets in the connectivity database.
162      */
163     int GetNetCount() const;
164 
165     /**
166      * Function GetRatsnestForNet()
167      * Returns the ratsnest, expressed as a set of graph edges for a given net.
168      */
169     RN_NET* GetRatsnestForNet( int aNet );
170 
171     /**
172      * Propagates the net codes from the source pads to the tracks/vias.
173      * @param aCommit is used to save the undo state of items modified by this call
174      * @param aMode controls how conflicts between pads are resolved
175      */
176     void PropagateNets( BOARD_COMMIT* aCommit = nullptr,
177                         PROPAGATE_MODE aMode = PROPAGATE_MODE::SKIP_CONFLICTS );
178 
179     bool CheckConnectivity( std::vector<CN_DISJOINT_NET_ENTRY>& aReport );
180 
181     /**
182      * Function FindIsolatedCopperIslands()
183      * Searches for copper islands in zone aZone that are not connected to any pad.
184      * @param aZone zone to test
185      * @param aIslands list of islands that have no connections (outline indices in the polygon set)
186      */
187     void FindIsolatedCopperIslands( ZONE* aZone, std::vector<int>& aIslands );
188     void FindIsolatedCopperIslands( std::vector<CN_ZONE_ISOLATED_ISLAND_LIST>& aZones );
189 
190     /**
191      * Function RecalculateRatsnest()
192      * Updates the ratsnest for the board.
193      * @param aCommit is used to save the undo state of items modified by this call
194      */
195     void RecalculateRatsnest( BOARD_COMMIT* aCommit = nullptr );
196 
197     /**
198      * Function GetUnconnectedCount()
199      * Returns the number of remaining edges in the ratsnest.
200      */
201     unsigned int GetUnconnectedCount() const;
202 
203     bool IsConnectedOnLayer( const BOARD_CONNECTED_ITEM* aItem,
204                              int aLayer, std::vector<KICAD_T> aTypes = {} ) const;
205 
206     unsigned int GetNodeCount( int aNet = -1 ) const;
207 
208     unsigned int GetPadCount( int aNet = -1 ) const;
209 
210     const std::vector<PCB_TRACK*> GetConnectedTracks( const BOARD_CONNECTED_ITEM* aItem ) const;
211 
212     const std::vector<PAD*> GetConnectedPads( const BOARD_CONNECTED_ITEM* aItem ) const;
213 
214     void GetConnectedPads( const BOARD_CONNECTED_ITEM* aItem, std::set<PAD*>* pads ) const;
215 
216     /**
217      * Function GetConnectedItemsAtAnchor()
218      * Returns a list of items connected to a source item aItem at position aAnchor
219      * with an optional maximum distance from the defined anchor.
220      * @param aItem is the reference item to find other connected items.
221      * @param aAnchor is the position to find connected items on.
222      * @param aTypes allows one to filter by item types.
223      * @param aMaxError Maximum distance of the found items' anchors to aAnchor in IU
224      * @return
225      */
226     const std::vector<BOARD_CONNECTED_ITEM*> GetConnectedItemsAtAnchor(
227             const BOARD_CONNECTED_ITEM* aItem,
228             const VECTOR2I& aAnchor,
229             const KICAD_T aTypes[],
230             const int& aMaxError = 0 ) const;
231 
232     void GetUnconnectedEdges( std::vector<CN_EDGE>& aEdges ) const;
233 
234     bool TestTrackEndpointDangling( PCB_TRACK* aTrack, wxPoint* aPos = nullptr );
235 
236     /**
237      * Function ClearDynamicRatsnest()
238      * Erases the temporary dynamic ratsnest (i.e. the ratsnest lines that
239      * pcbnew displays when moving an item/set of items)
240      */
241     void ClearDynamicRatsnest();
242 
243     /**
244      * Hides the temporary dynamic ratsnest lines.
245      */
246     void HideDynamicRatsnest();
247 
248     /**
249      * Function ComputeDynamicRatsnest()
250      * Calculates the temporary dynamic ratsnest (i.e. the ratsnest lines that)
251      * for the set of items aItems.
252      */
253     void ComputeDynamicRatsnest( const std::vector<BOARD_ITEM*>& aItems,
254                                  const CONNECTIVITY_DATA* aDynamicData,
255                                  VECTOR2I aInternalOffset = { 0, 0 } );
256 
GetDynamicRatsnest()257     const std::vector<RN_DYNAMIC_LINE>& GetDynamicRatsnest() const
258     {
259         return m_dynamicRatsnest;
260     }
261 
262     /**
263      * Function GetConnectedItems()
264      * Returns a list of items connected to a source item aItem.
265      * @param aItem is the reference item to find other connected items.
266      * @param aTypes allows one to filter by item types.
267      */
268     const std::vector<BOARD_CONNECTED_ITEM*> GetConnectedItems( const BOARD_CONNECTED_ITEM* aItem,
269             const KICAD_T aTypes[], bool aIgnoreNetcodes = false ) const;
270 
271     /**
272      * Function GetNetItems()
273      * Returns the list of items that belong to a certain net.
274      * @param aNetCode is the net code.
275      * @param aTypes allows one to filter by item types.
276      */
277     const std::vector<BOARD_CONNECTED_ITEM*> GetNetItems( int aNetCode,
278             const KICAD_T aTypes[] ) const;
279 
280     void BlockRatsnestItems( const std::vector<BOARD_ITEM*>& aItems );
281 
GetConnectivityAlgo()282     std::shared_ptr<CN_CONNECTIVITY_ALGO> GetConnectivityAlgo() const
283     {
284         return m_connAlgo;
285     }
286 
GetLock()287     KISPINLOCK& GetLock()
288     {
289         return m_lock;
290     }
291 
292     void MarkItemNetAsDirty( BOARD_ITEM* aItem );
293     void SetProgressReporter( PROGRESS_REPORTER* aReporter );
294 
GetNetclassMap()295     const std::map<int, wxString>& GetNetclassMap() const
296     {
297         return m_netclassMap;
298     }
299 
300 #ifndef SWIG
301     const std::vector<CN_EDGE> GetRatsnestForItems( const std::vector<BOARD_ITEM*> aItems );
302 
303     const std::vector<CN_EDGE> GetRatsnestForPad( const PAD* aPad );
304 
305     const std::vector<CN_EDGE> GetRatsnestForComponent( FOOTPRINT* aComponent,
306                                                         bool aSkipInternalConnections = false );
307 #endif
308 
GetFromToCache()309     std::shared_ptr<FROM_TO_CACHE> GetFromToCache()
310     {
311         return m_fromToCache;
312     }
313 
314 private:
315     void    updateRatsnest();
316 
317     void    addRatsnestCluster( const std::shared_ptr<CN_CLUSTER>& aCluster );
318 
319 private:
320     std::shared_ptr<CN_CONNECTIVITY_ALGO> m_connAlgo;
321 
322     std::shared_ptr<FROM_TO_CACHE>  m_fromToCache;
323     std::vector<RN_DYNAMIC_LINE>    m_dynamicRatsnest;
324     std::vector<RN_NET*>            m_nets;
325 
326     /// Used to suppress ratsnest calculations on dynamic ratsnests
327     bool                            m_skipRatsnest = false;
328 
329     KISPINLOCK                      m_lock;
330 
331     /// Map of netcode -> netclass the net is a member of; used for ratsnest painting
332     std::map<int, wxString>         m_netclassMap;
333 
334     PROGRESS_REPORTER*              m_progressReporter;
335 };
336 
337 #endif
338