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 The 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 <functional>
#include <memory>
#include <mutex>
#include <utility>
#include <vector>
#include <map>
 
#include <erc/erc_settings.h>
#include <gal/color4d.h>
#include <sch_connection.h>
#include <sch_item.h>
#include <sch_netchain.h>
#include <wx/treectrl.h>
#include <wx/string.h>
#include <advanced_config.h>
#include <progress_reporter.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 SCH_NETCHAIN;
 

class CONNECTION_SUBGRAPH
{
public:
    enum class PRIORITY
    {
        INVALID = -1,
        NONE    = 0,
        PIN,
        SHEET_PIN,
        HIER_LABEL,
        LOCAL_LABEL,
        LOCAL_POWER_PIN,
        GLOBAL_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 )
    {}
 
 
    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 ) 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;
    }
 
    const std::unordered_map< std::shared_ptr<SCH_CONNECTION>,
                        std::unordered_set<CONNECTION_SUBGRAPH*> >& GetBusParents() const
    {
        return m_bus_parents;
    }
 
    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
    SCH_CONNECTION* StoreImplicitConnection( std::unique_ptr<SCH_CONNECTION> aConnection )
    {
        SCH_CONNECTION* raw = aConnection.get();
 
        m_bus_element_connections.insert( std::move( aConnection ) );
 
        return raw;
    }
 
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::mutex m_driver_name_cache_mutex;
    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;
 
    // A comparator for unique_ptr<SCH_CONNECTION> to allow storage in a set
    struct CompareConnectionPtr
    {
        bool operator()( const std::unique_ptr<SCH_CONNECTION>& aLeft,
                         const std::unique_ptr<SCH_CONNECTION>& aRight ) const
        {
            return aLeft.get() < aRight.get();
        }
    };

    std::set<std::unique_ptr<SCH_CONNECTION>, CompareConnectionPtr> 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();
 
    // We own at least one list of raw pointers.  Don't let the compiler fill in copy c'tors that
    // will only land us in trouble.
    CONNECTION_GRAPH( const CONNECTION_GRAPH& ) = delete;
    CONNECTION_GRAPH& operator=( const CONNECTION_GRAPH& ) = delete;
 
    // Define QA friend functions to allow testing of private methods
    friend void boost_test_update_symbol_connectivity();
    friend void boost_test_update_generic_connectivity();
    friend void boost_test_inject_committed_net_chain( CONNECTION_GRAPH& aGraph,
                                                       std::unique_ptr<SCH_NETCHAIN> aChain );
    friend SCH_NETCHAIN* boost_test_resolve_potential_chain_by_terminals(
            const std::pair<std::pair<wxString, wxString>,
                            std::pair<wxString, wxString>>& aTerms,
            const std::map<std::pair<wxString, wxString>, wxString>& aRefPinToNet,
            const std::vector<std::unique_ptr<SCH_NETCHAIN>>& aPotentials,
            const wxString& aChainName );
 
    void Reset();
 
    void SetSchematic( SCHEMATIC* aSchematic )
    {
        m_schematic = aSchematic;
    }
 
    SCHEMATIC* GetSchematic() const { return m_schematic; }
 
    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,
                      PROGRESS_REPORTER* aProgressReporter = 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; }
 
    // (Deprecated accessor moved to potential net chains section; retained later.)
 
    SCH_NETCHAIN* GetNetChainForNet( const wxString& aNet );
    SCH_NETCHAIN* GetNetChainByName( const wxString& aName );
    void ReplaceNetChainTerminalPin( const wxString& aNetChain, const KIID& aPrev, const KIID& aNew );
    void SetNetChainTerminalOverrides( const std::map<wxString, std::pair<KIID, KIID>>& aOverrides );

    void SetNetChainNetClassOverrides( const std::map<wxString, wxString>& aOverrides )
    {
        m_netChainNetClassOverrides = aOverrides;
    }
 
    const std::map<wxString, wxString>& GetNetChainNetClassOverrides() const
    {
        return m_netChainNetClassOverrides;
    }
 
    struct CHAIN_TERMINAL_REF
    {
        wxString ref;
        wxString pin;
    };
    using CHAIN_TERMINAL_REFS = std::pair<CHAIN_TERMINAL_REF, CHAIN_TERMINAL_REF>;
 
    void SetNetChainTerminalRefOverrides( const std::map<wxString, CHAIN_TERMINAL_REFS>& aRefs )
    {
        m_netChainTerminalRefOverrides = aRefs;
    }
 
    const std::map<wxString, CHAIN_TERMINAL_REFS>& GetNetChainTerminalRefOverrides() const
    {
        return m_netChainTerminalRefOverrides;
    }
 
    const std::map<wxString, std::pair<KIID, KIID>>& GetNetChainTerminalOverrides() const
    {
        return m_netChainTerminalOverrides;
    }
 
    void SetNetChainColorOverrides( const std::map<wxString, COLOR4D>& aOverrides )
    {
        m_netChainColorOverrides = aOverrides;
    }
 
    const std::map<wxString, COLOR4D>& GetNetChainColorOverrides() const
    {
        return m_netChainColorOverrides;
    }

    void SetNetChainMemberNetOverrides( const std::map<wxString, std::set<wxString>>& aOverrides )
    {
        m_netChainMemberNetOverrides = aOverrides;
    }
 
    const std::map<wxString, std::set<wxString>>& GetNetChainMemberNetOverrides() const
    {
        return m_netChainMemberNetOverrides;
    }

    CONNECTION_SUBGRAPH* FindSubgraphByName( const wxString& aNetName,
                                             const SCH_SHEET_PATH& aPath );

    CONNECTION_SUBGRAPH* FindFirstSubgraphByName( const wxString& aNetName );
 
    CONNECTION_SUBGRAPH* GetSubgraphForItem( SCH_ITEM* aItem ) const;
 
    const std::vector<CONNECTION_SUBGRAPH*>& GetAllSubgraphs( const wxString& aNetName ) const;

    wxString GetResolvedSubgraphName( const CONNECTION_SUBGRAPH* aSubGraph ) const;

    static wxString MakeNetChainKey( const wxString& aRawNetName, long aSubgraphCode );

    static wxString MakeNetChainKey( const CONNECTION_SUBGRAPH* aSubGraph );

    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 );

    bool IsMinor() const
    {
        return static_cast<ssize_t>( m_items.size() )
               < ADVANCED_CFG::GetCfg().m_MinorSchematicGraphSize;
    }
 
private:

    void updateSymbolConnectivity( const SCH_SHEET_PATH& aSheet,
                                   SCH_SYMBOL* aSymbol,
                                   std::map<VECTOR2I, std::vector<SCH_ITEM*>>& aConnectionMap );

    void updatePinConnectivity( const SCH_SHEET_PATH& aSheet,
                                SCH_PIN* aPin,
                                SCH_CONNECTION* aConnection );

    void updateGenericItemConnectivity( const SCH_SHEET_PATH& aSheet,
                                        SCH_ITEM* aItem,
                                        std::map<VECTOR2I, std::vector<SCH_ITEM*>>& aConnectionMap );

    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 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 ercCheckDanglingWireEndpoints( const CONNECTION_SUBGRAPH* aSubgraph );

    void collectBusMemberSiblings( const CONNECTION_SUBGRAPH* aBusParent, const wxString& aMemberName,
                                   std::unordered_set<const CONNECTION_SUBGRAPH*>& aOut ) const;

    bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );

    int ercCheckDirectiveLabels();

    int ercCheckHierSheets();

    int ercCheckSingleGlobalLabel();

    size_t hasPins( const CONNECTION_SUBGRAPH* aLocSubgraph );
 
    void RebuildNetChains();
 
    // Potential net chain (inferred) API -------------------------------
public:
    const std::vector<std::unique_ptr<SCH_NETCHAIN>>& GetPotentialNetChains() const { return m_potentialNetChains; }

    SCH_NETCHAIN* FindPotentialNetChainBetweenPins( SCH_PIN* aPinA, SCH_PIN* aPinB );

    SCH_NETCHAIN* CreateNetChainFromPotential( SCH_NETCHAIN* aPotential, const wxString& aName );

    SCH_NETCHAIN* CreateManualNetChain( const wxString& aName,
                                        const std::set<class SCH_SYMBOL*>& aSymbols,
                                        const std::set<wxString>& aNets,
                                        const KIID& aTerminalPinA, const KIID& aTerminalPinB,
                                        const wxString& aRefA, const wxString& aPinNumA,
                                        const wxString& aRefB, const wxString& aPinNumB );

    const std::vector<std::unique_ptr<SCH_NETCHAIN>>& GetCommittedNetChains() const { return m_committedNetChains; }

    void ApplyNetChainNetclasses();

    bool NetChainsBuilt() const { return m_netChainsBuilt; }

    static std::function<void( CONNECTION_GRAPH& )>& RebuildNetChainsTestHook();

    bool DeleteCommittedNetChain( const wxString& aName );

    bool RenameCommittedNetChain( const wxString& aOld, const wxString& aNew );
 
private:
    static SCH_NETCHAIN* resolvePotentialChainByTerminals(
            const CHAIN_TERMINAL_REFS& aTermRefs,
            const std::map<std::pair<wxString, wxString>, wxString>& aRefPinToNet,
            const std::vector<std::unique_ptr<SCH_NETCHAIN>>& aPotentials,
            const wxString& aChainName );

    void rekeyOverrideMaps( const wxString& aOld, const wxString& aNew );

    void refreshCommittedChainPayload( SCH_NETCHAIN* aTarget, const std::set<wxString>& aNets,
                                       const std::set<class SCH_SYMBOL*>& aSymbols,
                                       const KIID& aTerminalPinA, const KIID& aTerminalPinB,
                                       const wxString& aRefA, const wxString& aPinNumA,
                                       const wxString& aRefB, const wxString& aPinNumB );

    void refreshCommittedChainFromPotential( SCH_NETCHAIN* aTarget, const SCH_NETCHAIN& aSource );
 
    // Bridge-graph helper types shared by RebuildNetChains() and FindNetChainPathsBetweenPins().
    // A bridge edge represents a 2-pin passthrough symbol that ties two distinct subgraph nets
    // together; the bridge graph is the adjacency built from the surviving (non-power-touching)
    // edges after the leaf-prune pass.
 
    struct BRIDGE_EDGE
    {
        wxString             a;
        wxString             b;
        class SCH_SYMBOL*    sym;
    };
 
    struct BRIDGE_NEIGHBOR
    {
        wxString             other;
        class SCH_SYMBOL*    sym;
    };
 
    struct BRIDGE_GRAPH
    {
        std::map<wxString, std::vector<BRIDGE_NEIGHBOR>> adjacency;
        std::vector<BRIDGE_EDGE>                         edges;
    };

    BRIDGE_GRAPH buildBridgeAdjacency();

    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;
 
    std::vector<std::unique_ptr<SCH_NETCHAIN>> m_committedNetChains;
    std::vector<std::unique_ptr<SCH_NETCHAIN>> m_potentialNetChains; 
    bool                                       m_netChainsBuilt = false;
    std::map<wxString, std::pair<KIID, KIID>> m_netChainTerminalOverrides;
    std::map<wxString, wxString>              m_netChainNetClassOverrides;
    std::map<wxString, COLOR4D>               m_netChainColorOverrides;
    std::map<wxString, CHAIN_TERMINAL_REFS>    m_netChainTerminalRefOverrides;
    std::map<wxString, std::set<wxString>>    m_netChainMemberNetOverrides;
 
    int m_last_net_code;
 
    int m_last_bus_code;
 
    int m_last_subgraph_code;
 
    SCHEMATIC* m_schematic;     
};
 
#endif