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 <mutex>
#include <utility>
#include <vector>
 
#include <erc/erc_settings.h>
#include <sch_connection.h>
#include <sch_item.h>
#include <wx/treectrl.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 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 )
    {}
 
    ~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 ) 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
    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::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;

    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();
    }
 
    // 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();
 
    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,
                      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; }

    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;

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

    bool ercCheckLabels( const CONNECTION_SUBGRAPH* aSubgraph );

    int ercCheckDirectiveLabels();

    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