KiCad PCB EDA Suite
from_to_cache.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2004-2020 KiCad Developers.
5  *
6  * This program is free software: you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License as published by the
8  * Free Software Foundation, either version 3 of the License, or (at your
9  * option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License along
17  * with this program. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #include <cstdio>
21 #include <memory>
22 #include <reporter.h>
23 #include <board.h>
24 #include <track.h>
25 #include <kicad_string.h>
26 
27 #include <pcb_expr_evaluator.h>
28 
31 
33 
35 {
36  m_ftEndpoints.clear();
37 
38  for( FOOTPRINT* footprint : m_board->Footprints() )
39  {
40  for( PAD* pad : footprint->Pads() )
41  {
42  FT_ENDPOINT ent;
43  ent.name = footprint->GetReference() + "-" + pad->GetName();
44  ent.parent = pad;
45  m_ftEndpoints.push_back( ent );
46  ent.name = footprint->GetReference();
47  ent.parent = pad;
48  m_ftEndpoints.push_back( ent );
49  }
50  }
51 }
52 
53 
55  PS_OK = 0,
58 };
59 
60 
61 static bool isVertexVisited( CN_ITEM* v, const std::vector<CN_ITEM*>& path )
62 {
63  for( auto u : path )
64  {
65  if ( u == v )
66  return true;
67  }
68 
69  return false;
70 }
71 
72 
73 static PATH_STATUS uniquePathBetweenNodes( CN_ITEM* u, CN_ITEM* v, std::vector<CN_ITEM*>& outPath )
74 {
75  using Path = std::vector<CN_ITEM*>;
76  std::deque<Path> Q;
77 
78  Path pInit;
79  int pathFound = false;
80  pInit.push_back( u );
81  Q.push_back( pInit );
82 
83  while( Q.size() )
84  {
85  Path path = Q.front();
86  Q.pop_front();
87  CN_ITEM* last = path.back();
88 
89  if( last == v )
90  {
91  outPath = path;
92  if( pathFound )
93  return PS_MULTIPLE_PATHS;
94  pathFound = true;
95  }
96 
97  for( auto ci : last->ConnectedItems() )
98  {
99  bool vertexVisited = isVertexVisited( ci, path );
100 
101  for( auto& p : Q )
102  if( isVertexVisited( ci, p ) )
103  {
104  vertexVisited = true;
105  break;
106  }
107 
108  if( !vertexVisited )
109  {
110  Path newpath( path );
111  newpath.push_back( ci );
112  Q.push_back( newpath );
113  }
114  }
115  }
116 
117  return pathFound ? PS_OK : PS_NO_PATH;
118 };
119 
120 
121 int FROM_TO_CACHE::cacheFromToPaths( const wxString& aFrom, const wxString& aTo )
122 {
123  std::vector<FT_PATH> paths;
124  auto connectivity = m_board->GetConnectivity();
125  auto cnAlgo = connectivity->GetConnectivityAlgo();
126 
127  for( auto& endpoint : m_ftEndpoints )
128  {
129  if( WildCompareString( aFrom, endpoint.name, false ) )
130  {
131  FT_PATH p;
132  p.net = endpoint.parent->GetNetCode();
133  p.from = endpoint.parent;
134  p.to = nullptr;
135  paths.push_back(p);
136  }
137  }
138 
139  for( auto &path : paths )
140  {
141  int count = 0;
142  auto netName = path.from->GetNetname();
143 
144  wxString fromName = path.from->GetParent()->GetReference() + "-" + path.from->GetName();
145 
146  const KICAD_T onlyRouting[] = { PCB_PAD_T, PCB_ARC_T, PCB_VIA_T, PCB_TRACE_T, EOT };
147 
148  auto padCandidates = connectivity->GetConnectedItems( path.from, onlyRouting );
149  PAD* toPad = nullptr;
150 
151  for( auto pitem : padCandidates )
152  {
153  if( pitem == path.from )
154  continue;
155 
156  if( pitem->Type() != PCB_PAD_T )
157  continue;
158 
159  PAD *pad = static_cast<PAD*>( pitem );
160 
161  wxString toName = pad->GetParent()->GetReference() + "-" + pad->GetName();
162 
163 
164  for ( auto& endpoint : m_ftEndpoints )
165  {
166  if( pad == endpoint.parent )
167  {
168  if( WildCompareString( aTo, endpoint.name, false ) )
169  {
170  count++;
171  toPad = endpoint.parent;
172 
173  path.to = toPad;
174  path.fromName = fromName;
175  path.toName = toName;
176  path.fromWildcard = aFrom;
177  path.toWildcard = aTo;
178 
179  if( count >= 2 )
180  {
181  // fixme: report this somewhere?
182  //printf("Multiple targets found, aborting...\n");
183  path.to = nullptr;
184  }
185  }
186  }
187  }
188  }
189  }
190 
191  int newPaths = 0;
192 
193  for( auto &path : paths )
194  {
195  if( !path.from || !path.to )
196  continue;
197 
198 
199  CN_ITEM *cnFrom = cnAlgo->ItemEntry( path.from ).GetItems().front();
200  CN_ITEM *cnTo = cnAlgo->ItemEntry( path.to ).GetItems().front();
202 
203  auto result = uniquePathBetweenNodes( cnFrom, cnTo, upath );
204 
205  if( result == PS_OK )
206  path.isUnique = true;
207  else
208  path.isUnique = false;
209 
210 
211  //printf( "%s\n", (const char *) wxString::Format( _("Check path: %s -> %s (net %s)"), path.fromName, path.toName, cnFrom->Parent()->GetNetname() ) );
212 
213  if( result == PS_NO_PATH )
214  continue;
215 
216  for( auto item : upath )
217  {
218  path.pathItems.insert( item->Parent() );
219  }
220 
221  m_ftPaths.push_back(path);
222  newPaths++;
223  }
224 
225  //reportAux( _("Cached %d paths\n"), newPaths );
226 
227  return newPaths;
228 }
229 
230 bool FROM_TO_CACHE::IsOnFromToPath( BOARD_CONNECTED_ITEM* aItem, const wxString& aFrom, const wxString& aTo )
231 {
232  int nFromTosFound = 0;
233 
234  if( !m_board )
235  return false;
236 
237  //printf("Check %d cached paths [%p]\n", m_ftPaths.size(), aItem );
238  for( int attempt = 0; attempt < 2; attempt++ )
239  {
240  // item already belongs to path
241  for( auto& ftPath : m_ftPaths )
242  {
243  if( aFrom == ftPath.fromWildcard &&
244  aTo == ftPath.toWildcard )
245  {
246  nFromTosFound++;
247 
248  if( ftPath.pathItems.count( aItem ) )
249  {
250  // printf("Found cached path for %p [%s->%s]\n", aItem, (const char *)ftPath.fromName, (const char *) ftPath.toName );
251  return true;
252  }
253  }
254  }
255 
256  if( !nFromTosFound )
257  cacheFromToPaths( aFrom, aTo );
258  else
259  return false;
260  }
261 
262  return false;
263 }
264 
265 
267 {
268  m_board = aBoard;
270  m_ftPaths.clear();
271 }
272 
273 
274 FROM_TO_CACHE::FT_PATH* FROM_TO_CACHE::QueryFromToPath( const std::set<BOARD_CONNECTED_ITEM*>& aItems )
275 {
276  for( auto& ftPath : m_ftPaths )
277  {
278  if ( ftPath.pathItems == aItems )
279  return &ftPath;
280  }
281 
282  return nullptr;
283 }
std::vector< CN_ITEM * > CONNECTED_ITEMS
const CONNECTED_ITEMS & ConnectedItems() const
std::vector< FT_ENDPOINT > m_ftEndpoints
Definition: from_to_cache.h:68
class ARC, an arc track segment on a copper layer
Definition: typeinfo.h:98
static bool isVertexVisited(CN_ITEM *v, const std::vector< CN_ITEM * > &path)
wxString GetNetname() const
Function GetNetname.
BOARD * m_board
Definition: from_to_cache.h:71
class PAD, a pad in a footprint
Definition: typeinfo.h:90
BOARD_CONNECTED_ITEM is a base class derived from BOARD_ITEM for items that can be connected and have...
search types array terminator (End Of Types)
Definition: typeinfo.h:82
KICAD_T
Enum KICAD_T is the set of class identification values, stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:78
class TRACK, a track segment (segment on a copper layer)
Definition: typeinfo.h:96
std::vector< FT_PATH > m_ftPaths
Definition: from_to_cache.h:69
void Rebuild(BOARD *aBoard)
int cacheFromToPaths(const wxString &aFrom, const wxString &aTo)
bool WildCompareString(const wxString &pattern, const wxString &string_to_tst, bool case_sensitive)
Compare a string against wild card (* and ?) pattern using the usual rules.
Definition: string.cpp:488
static PATH_STATUS uniquePathBetweenNodes(CN_ITEM *u, CN_ITEM *v, std::vector< CN_ITEM * > &outPath)
FOOTPRINTS & Footprints()
Definition: board.h:283
std::shared_ptr< CONNECTIVITY_DATA > GetConnectivity() const
Return a list of missing connections between components/tracks.
Definition: board.h:382
const wxString & GetName() const
Definition: pad.h:127
PATH_STATUS
const wxString GetReference() const
Function GetReference.
Definition: footprint.h:440
FOOTPRINT * GetParent() const
bool IsOnFromToPath(BOARD_CONNECTED_ITEM *aItem, const wxString &aFrom, const wxString &aTo)
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:186
void buildEndpointList()
class VIA, a via (like a track segment on a copper layer)
Definition: typeinfo.h:97
Definition: pad.h:59
FT_PATH * QueryFromToPath(const std::set< BOARD_CONNECTED_ITEM * > &aItems)