connection_graph.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2018 CERN
 * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
 * @author Jon Evans <[email protected]>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program. If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef _CONNECTION_GRAPH_H
#define _CONNECTION_GRAPH_H
 
#include <mutex>
#include <utility>
#include <vector>
 
#include <erc_settings.h>
#include <sch_connection.h>
#include <sch_item.h>
#include <wx/treectrl.h>
 
 
#ifdef DEBUG
// Uncomment this line to enable connectivity debugging features
// #define CONNECTIVITY_DEBUG
#endif
 
 
class CONNECTION_GRAPH;
class SCHEMATIC;
class SCH_EDIT_FRAME;
class SCH_HIERLABEL;
class SCH_PIN;
class SCH_SHEET_PIN;
 
 
class CONNECTION_SUBGRAPH
{
public:
 enum class PRIORITY
 {
 INVALID = -1,
 NONE = 0,
 PIN,
 SHEET_PIN,
 HIER_LABEL,
 LOCAL_LABEL,
 POWER_PIN,
 GLOBAL
 };
 
 explicit CONNECTION_SUBGRAPH( CONNECTION_GRAPH* aGraph ) :
 m_graph( aGraph ),
 m_dirty( false ),
 m_absorbed( false ),
 m_is_bus_member( false ),
 m_absorbed_by( nullptr ),
 m_code( -1 ),
 m_multiple_drivers( false ),
 m_strong_driver( false ),
 m_local_driver( false ),
 m_bus_entry( nullptr ),
 m_hier_parent( nullptr ),
 m_driver( nullptr ),
 m_no_connect( nullptr ),
 m_driver_connection( nullptr )
 {}
 
 ~CONNECTION_SUBGRAPH()
 {
 for( SCH_CONNECTION* connection : m_bus_element_connections )
 delete connection;
 }
 
 friend class CONNECTION_GRAPH;
 
 bool ResolveDrivers( bool aCheckMultipleDrivers = false );
 
 wxString GetNetName() const;
 
 std::vector<SCH_ITEM*> GetVectorBusLabels() const;
 
 std::vector<SCH_ITEM*> GetAllBusLabels() const;
 
 const wxString& GetNameForDriver( SCH_ITEM* aItem ) const;
 
 const std::vector<std::pair<wxString, SCH_ITEM*>>
 GetNetclassesForDriver( SCH_ITEM* aItem, bool returnAll ) const;
 
 void Absorb( CONNECTION_SUBGRAPH* aOther );
 
 void AddItem( SCH_ITEM* aItem );
 
 void UpdateItemConnections();
 
 const std::set<SCH_ITEM*>& GetItems() const
 {
 return m_items;
 }
 
 void getAllConnectedItems( std::set<std::pair<SCH_SHEET_PATH, SCH_ITEM*>>& aItems,
 std::set<CONNECTION_SUBGRAPH*>& aSubgraphs );
 
 static PRIORITY GetDriverPriority( SCH_ITEM* aDriver );
 
 PRIORITY GetDriverPriority()
 {
 if( m_driver )
 return GetDriverPriority( m_driver );
 else
 return PRIORITY::NONE;
 }
 
 const SCH_ITEM* GetDriver() const
 {
 return m_driver;
 }
 
 const SCH_CONNECTION* GetDriverConnection() const
 {
 return m_driver_connection;
 }
 
 const SCH_ITEM* GetNoConnect() const
 {
 return m_no_connect;
 }
 
 const SCH_SHEET_PATH& GetSheet() const
 {
 return m_sheet;
 }
 
 void RemoveItem( SCH_ITEM* aItem );
 
 void ExchangeItem( SCH_ITEM* aOldItem, SCH_ITEM* aNewItem );
 
 // Use this to keep a connection pointer that is not owned by any item
 // This will be destroyed with the subgraph
 void StoreImplicitConnection( SCH_CONNECTION* aConnection )
 {
 m_bus_element_connections.insert( aConnection );
 }
 
private:
 wxString driverName( SCH_ITEM* aItem ) const;
 
 CONNECTION_GRAPH* m_graph;
 
 bool m_dirty;
 
 bool m_absorbed;
 
 bool m_is_bus_member;
 
 CONNECTION_SUBGRAPH* m_absorbed_by;
 
 std::set<CONNECTION_SUBGRAPH*> m_absorbed_subgraphs;
 
 long m_code;
 
 bool m_multiple_drivers;
 
 bool m_strong_driver;
 
 bool m_local_driver;
 
 SCH_ITEM* m_bus_entry;
 
 std::set<SCH_ITEM*> m_drivers;
 
 std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
 std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_neighbors;
 
 std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
 std::unordered_set<CONNECTION_SUBGRAPH*> > m_bus_parents;
 
 std::set<SCH_SHEET_PIN*> m_hier_pins;
 
 std::set<SCH_HIERLABEL*> m_hier_ports;
 
 CONNECTION_SUBGRAPH* m_hier_parent;
 
 std::unordered_set<CONNECTION_SUBGRAPH*> m_hier_children;
 
 mutable std::unordered_map<SCH_ITEM*, wxString> m_driver_name_cache;
 
 SCH_ITEM* m_driver;
 
 std::set<SCH_ITEM*> m_items;
 
 SCH_ITEM* m_no_connect;
 
 SCH_SHEET_PATH m_sheet;
 
 SCH_CONNECTION* m_driver_connection;
 
 std::set<SCH_CONNECTION*> m_bus_element_connections;
 
 std::mutex m_driver_mutex;
};
 
struct NET_NAME_CODE_CACHE_KEY
{
 wxString Name;
 int Netcode;
 
 bool operator==(const NET_NAME_CODE_CACHE_KEY& other) const
 {
 return Name == other.Name && Netcode == other.Netcode;
 }
};
 
namespace std
{
 template <>
 struct hash<NET_NAME_CODE_CACHE_KEY>
 {
 std::size_t operator()( const NET_NAME_CODE_CACHE_KEY& k ) const
 {
 const std::size_t prime = 19937;
 
 return hash<wxString>()( k.Name ) ^ ( hash<int>()( k.Netcode ) * prime );
 }
 };
}
 
typedef std::unordered_map<NET_NAME_CODE_CACHE_KEY, std::vector<CONNECTION_SUBGRAPH*>> NET_MAP;
 
class CONNECTION_GRAPH
{
public:
 CONNECTION_GRAPH( SCHEMATIC* aSchematic = nullptr ) :
 m_last_net_code( 1 ),
 m_last_bus_code( 1 ),
 m_last_subgraph_code( 1 ),
 m_schematic( aSchematic )
 {}
 
 ~CONNECTION_GRAPH()
 {
 Reset();
 }
 
 void Reset();
 
 void SetSchematic( SCHEMATIC* aSchematic )
 {
 m_schematic = aSchematic;
 }
 
 void SetLastCodes( const CONNECTION_GRAPH* aOther )
 {
 m_last_net_code = aOther->m_last_net_code;
 m_last_bus_code = aOther->m_last_bus_code;
 m_last_subgraph_code = aOther->m_last_subgraph_code;
 }
 
 void Recalculate( const SCH_SHEET_LIST& aSheetList, bool aUnconditional = false,
 std::function<void( SCH_ITEM* )>* aChangedItemHandler = nullptr );
 
 std::shared_ptr<BUS_ALIAS> GetBusAlias( const wxString& aName );
 
 std::vector<const CONNECTION_SUBGRAPH*> GetBusesNeedingMigration();
 
 int RunERC();
 
 const NET_MAP& GetNetMap() const { return m_net_code_to_subgraphs_map; }
 
 CONNECTION_SUBGRAPH* FindSubgraphByName( const wxString& aNetName,
 const SCH_SHEET_PATH& aPath );
 
 CONNECTION_SUBGRAPH* FindFirstSubgraphByName( const wxString& aNetName );
 
 CONNECTION_SUBGRAPH* GetSubgraphForItem( SCH_ITEM* aItem );
 
 const std::vector<CONNECTION_SUBGRAPH*> GetAllSubgraphs( const wxString& aNetName ) const;
 
 wxString GetResolvedSubgraphName( const CONNECTION_SUBGRAPH* aSubGraph ) const;
 
 std::set<std::pair<SCH_SHEET_PATH, SCH_ITEM*>> ExtractAffectedItems(
 const std::set<SCH_ITEM*> &aItems );
 
 void Merge( CONNECTION_GRAPH& aGraph );
 
 void RemoveItem( SCH_ITEM* aItem );
 
 void ExchangeItem( SCH_ITEM* aOldItem, SCH_ITEM* aNewItem );
 
private:
 void updateItemConnectivity( const SCH_SHEET_PATH& aSheet,
 const std::vector<SCH_ITEM*>& aItemList );
 
 void buildConnectionGraph( std::function<void( SCH_ITEM* )>* aChangedItemHandler, bool aUnconditional );
 
 void buildItemSubGraphs();
 
 void resolveAllDrivers();
 
 void collectAllDriverValues();
 
 void generateGlobalPowerPinSubGraphs();
 
 void generateBusAliasMembers();
 
 void processSubGraphs();
 
 int assignNewNetCode( SCH_CONNECTION& aConnection );
 
 int getOrCreateNetCode( const wxString& aNetName );
 
 void assignNetCodesToBus( SCH_CONNECTION* aConnection );
 
 void propagateToNeighbors( CONNECTION_SUBGRAPH* aSubgraph, bool aForce );
 
 void removeSubgraphs( std::set<CONNECTION_SUBGRAPH*>& aSubgraphs );
 
 static SCH_CONNECTION* matchBusMember( SCH_CONNECTION* aBusConnection,
 SCH_CONNECTION* aSearch );
 
 std::shared_ptr<SCH_CONNECTION> getDefaultConnection( SCH_ITEM* aItem,
 CONNECTION_SUBGRAPH* aSubgraph );
 
 void recacheSubgraphName( CONNECTION_SUBGRAPH* aSubgraph, const wxString& aOldName );
 
 bool ercCheckMultipleDrivers( const CONNECTION_SUBGRAPH* aSubgraph );
 
 bool ercCheckNetclassConflicts( const std::vector<CONNECTION_SUBGRAPH*>& subgraphs );
 
 bool ercCheckBusToNetConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
 
 bool ercCheckBusToBusConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
 
 bool ercCheckBusToBusEntryConflicts( const CONNECTION_SUBGRAPH* aSubgraph );
 
 bool ercCheckNoConnects( const CONNECTION_SUBGRAPH* aSubgraph );
 
 bool ercCheckFloatingWires( const CONNECTION_SUBGRAPH* aSubgraph );
 
 bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );
 
 int ercCheckHierSheets();
 
 int ercCheckSingleGlobalLabel();
 
 size_t hasPins( const CONNECTION_SUBGRAPH* aLocSubgraph );
 
 
private:
 SCH_SHEET_LIST m_sheetList;
 
 std::vector<SCH_ITEM*> m_items;
 
 std::vector<CONNECTION_SUBGRAPH*> m_subgraphs;
 
 std::vector<CONNECTION_SUBGRAPH*> m_driver_subgraphs;
 
 std::unordered_map<SCH_SHEET_PATH, std::vector<CONNECTION_SUBGRAPH*>> m_sheet_to_subgraphs_map;
 
 std::vector<std::pair<SCH_SHEET_PATH, SCH_PIN*>> m_global_power_pins;
 
 std::unordered_map<wxString, std::shared_ptr<BUS_ALIAS>> m_bus_alias_cache;
 
 std::unordered_map<wxString, int> m_net_name_to_code_map;
 
 std::unordered_map<wxString, int> m_bus_name_to_code_map;
 
 std::unordered_map<wxString, std::vector<const CONNECTION_SUBGRAPH*>> m_global_label_cache;
 
 std::map< std::pair<SCH_SHEET_PATH, wxString>,
 std::vector<const CONNECTION_SUBGRAPH*> > m_local_label_cache;
 
 std::unordered_map<wxString, std::vector<CONNECTION_SUBGRAPH*>> m_net_name_to_subgraphs_map;
 
 std::unordered_map<SCH_ITEM*, CONNECTION_SUBGRAPH*> m_item_to_subgraph_map;
 
 NET_MAP m_net_code_to_subgraphs_map;
 
 int m_last_net_code;
 
 int m_last_bus_code;
 
 int m_last_subgraph_code;
 
 SCHEMATIC* m_schematic; 
};
 
#endif