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