TORC: torc/utils/PhysicalDiff.hpp Source File

00001 // Torc - Copyright 2011 University of Southern California.  All Rights Reserved.
00002 // $HeadURL: https://torc-isi.svn.sourceforge.net/svnroot/torc-isi/branches/staging/0.9/src/torc/utils/PhysicalDiff.hpp $
00003 // $Id: PhysicalDiff.hpp 10 2011-10-12 18:40:16Z nsteiner $
00004 
00005 // This program is free software: you can redistribute it and/or modify it under the terms of the 
00006 // GNU General Public License as published by the Free Software Foundation, either version 3 of the 
00007 // License, or (at your option) any later version.
00008 // 
00009 // This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
00010 // without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See 
00011 // the GNU General Public License for more details.
00012 // 
00013 // You should have received a copy of the GNU General Public License along with this program.  If 
00014 // not, see <http://www.gnu.org/licenses/>.
00015 
00016 /// \file
00017 /// \brief PhysicalDiff class for comparing physical netlists.
00018 
00019 #ifndef TORC_UTILS_PHYSICALDIFF_HPP
00020 #define TORC_UTILS_PHYSICALDIFF_HPP
00021 
00022 #include <iostream>
00023 #include "torc/Physical.hpp"
00024 #include "torc/physical/OutputStreamHelpers.hpp"
00025 #include <vector>
00026 
00027 namespace torc {
00028 
00029 namespace utils {
00030     // forward declarations of unit test classes within their namespace.
00031     class PhysicalDiffDesignUnitTest;
00032     class PhysicalDiffModuleUnitTest;
00033     class PhysicalDiffCircuitUnitTest;
00034     class PhysicalDiffConfigMapUnitTest;
00035     class PhysicalDiffInstanceUnitTest;
00036     class PhysicalDiffNetUnitTest;
00037 }
00038 
00039 
00040 /// \brief Diff utility class for comparing physical netlists.
00041 /// \details This class takes two design pointers and compares them.
00042 class PhysicalDiff {
00043     /// \brief Unit test access to internal functions.
00044     friend class utils::PhysicalDiffDesignUnitTest;
00045     /// \brief Unit test access to internal functions.
00046     friend class utils::PhysicalDiffModuleUnitTest;
00047     /// \brief Unit test access to internal functions.
00048     friend class utils::PhysicalDiffCircuitUnitTest;
00049     /// \brief Unit test access to internal functions.
00050     friend class utils::PhysicalDiffConfigMapUnitTest;
00051     /// \brief Unit test access to internal functions.
00052     friend class utils::PhysicalDiffInstanceUnitTest;
00053     /// \brief Unit test access to internal functions.
00054     friend class utils::PhysicalDiffNetUnitTest;
00055 protected:
00056     /// \brief Imported type name.
00057     typedef std::string string;
00058     /// \brief Imported type name.
00059     typedef torc::physical::DesignSharedPtr DesignSharedPtr;
00060     /// \brief Imported type name.
00061     typedef torc::physical::ModuleSharedPtr ModuleSharedPtr;
00062     /// \brief Imported type name.
00063     typedef std::vector<ModuleSharedPtr> ModuleSharedPtrVector;
00064     /// \brief Imported type name.
00065     typedef torc::physical::CircuitSharedPtr CircuitSharedPtr;
00066     /// \brief Imported type name.
00067     typedef torc::physical::InstanceSharedPtr InstanceSharedPtr;
00068     /// \brief Imported type name.
00069     typedef std::vector<InstanceSharedPtr> InstanceSharedPtrVector;
00070     /// \brief Imported type name.
00071     typedef torc::physical::NetSharedPtr NetSharedPtr;
00072     /// \brief Imported type name.
00073     typedef std::vector<NetSharedPtr> NetSharedPtrVector;
00074     /// \brief Imported type name.
00075     typedef torc::physical::Circuit::InstanceSharedPtrConstIterator InstanceSharedPtrConstIterator;
00076     /// \brief Imported type name.
00077     typedef torc::physical::Circuit::InstanceSharedPtrIterator InstanceSharedPtrIterator;
00078     /// \brief Imported type name.
00079     typedef torc::physical::Circuit::NetSharedPtrConstIterator NetSharedPtrConstIterator;
00080     /// \brief Imported type name.
00081     typedef torc::physical::Circuit::NetSharedPtrIterator NetSharedPtrIterator;
00082     /// \brief Imported type name.
00083     typedef torc::physical::InstanceWeakPtr InstanceWeakPtr;
00084     /// \brief Imported type name.
00085     typedef torc::physical::Design::ModuleSharedPtrConstIterator ModuleSharedPtrConstIterator;
00086     /// \brief Imported type name.
00087     typedef torc::physical::Design::ModuleSharedPtrIterator ModuleSharedPtrIterator;
00088     /// \brief Imported type name.
00089     typedef torc::physical::ConfigMap::const_iterator ConfigMapConstIterator;
00090     /// \brief Imported type name.
00091     typedef torc::physical::Net::InstancePinSharedPtrConstIterator 
00092         InstancePinSharedPtrConstIterator;
00093     /// \brief Imported type name.
00094     typedef torc::physical::Net::PipConstIterator PipConstIterator;
00095     /// \brief Imported type name.
00096     typedef boost::shared_ptr<torc::physical::Named> NamedSharedPtr;
00097     /// \brief Imported type name.
00098     typedef boost::shared_ptr<torc::physical::ConfigMap> ConfigMapSharedPtr;
00099     /// \brief Imported type name.
00100     typedef torc::physical::Module::PortSharedPtrConstIterator PortSharedPtrConstIterator;
00101 
00102     /// \brief Output stream to use for comparison results.
00103     std::ostream& mStream;
00104     
00105 public:
00106     /// \todo Improve Pip comparison.
00107     /// \todo Port comparison should use port name.
00108     /// \todo Config sequence index is not used.
00109     /// \todo Instance does not check the reference pointer.
00110     PhysicalDiff(std::ostream& inOutStream) : mStream(inOutStream)
00111     {
00112         mStream << "WARNING: Pip comparison uses only tile, source, direction "
00113             << "and sink!" << std::endl;
00114         mStream << "WARNING: Port comparison does not use the port name!" << std::endl;
00115         mStream << "WARNING: Config sequence index not used!" << std::endl;
00116         mStream << "WARNING: Instance does not check reference pointer!" << std::endl;
00117     }
00118 
00119     /// \brief Top level call to diff two designs.
00120     bool diff(const DesignSharedPtr& left, const DesignSharedPtr& right) {
00121         return diffDesign(left, right);
00122     }
00123 protected:
00124     /// \brief Diff design pointers and then recursively compare modules and inherited members.
00125     bool diffDesign(const DesignSharedPtr& left, const DesignSharedPtr& right) {
00126         bool rval = true;
00127         string designNameLeft = left->getName();
00128         string designNameRight = right->getName();
00129 
00130         if (!(designNameLeft == designNameRight)) {
00131             mStream << "! Design Name: " << designNameLeft << " | " 
00132                 << designNameRight << std::endl;
00133             rval = false;
00134         }
00135         if (!(left->getDevice() == right->getDevice())) {
00136             mStream << "! Device: " << left->getDevice() << " | " 
00137                 << right->getDevice() << std::endl;
00138             rval = false;
00139         }
00140         if (!(left->getPackage() == right->getPackage())) {
00141             mStream << "! Package: " << left->getPackage() << " | "
00142                 << right->getPackage() << std::endl;
00143             rval = false;
00144         }
00145         if (!(left->getSpeedGrade() == right->getSpeedGrade())) {
00146             mStream << "! Speed grade: " << left->getSpeedGrade() 
00147                 << " | " << right->getSpeedGrade() << std::endl;
00148             rval = false;
00149         }
00150         if (!(left->getXdlVersion() == right->getXdlVersion())) {
00151             mStream << "! XDL version differs: " << left->getXdlVersion() 
00152                 << " | " << right->getXdlVersion() << std::endl;
00153             rval = false;
00154         }
00155         
00156         ModuleSharedPtrVector leftModules;
00157         ModuleSharedPtrVector rightModules;
00158         
00159         for (ModuleSharedPtrConstIterator p = left->modulesBegin(); p!= left->modulesEnd(); p++) {
00160             leftModules.push_back(*p);
00161         }
00162         for (ModuleSharedPtrConstIterator p = right->modulesBegin(); p!= right->modulesEnd(); p++) {
00163             rightModules.push_back(*p);
00164         }
00165         
00166         // look left to right
00167         ModuleSharedPtrIterator ileft;
00168         ModuleSharedPtrIterator iright;
00169         for (ileft = leftModules.begin(); ileft != leftModules.end(); ileft++) {
00170             bool found = false;
00171             for (iright = rightModules.begin(); iright != rightModules.end(); iright++) {
00172                 if ((*ileft)->getName() == (*iright)->getName()) {
00173                     found = true;
00174                     break;
00175                 }
00176             }
00177             if (found) {
00178                 rval = diffModule(*ileft, *iright) && rval;
00179                 rightModules.erase(iright);
00180             } else {
00181                 mStream << "< Module " << (*ileft)->getName() << std::endl;
00182                 rval = false;
00183             }
00184         }
00185         // anything left on the right doesn't appear on the left
00186         for (iright = rightModules.begin(); iright != rightModules.end(); iright++) {
00187             mStream << "> Module " << (*iright)->getName() << std::endl;
00188             rval = false;
00189         }
00190         // A design is a circuit
00191         rval = diffCircuit(left, right) && rval;
00192         return rval;
00193     }
00194     /// \brief Diff module pointers and then recursively compare inherited members from circuit.
00195     bool diffModule(const ModuleSharedPtr& left, const ModuleSharedPtr& right) {
00196         bool rval = true;
00197         
00198         if (!(left->getAnchor() == right->getAnchor())) {
00199             mStream << "! Module " << left->getName() << " anchor: " << left->getAnchor()
00200                 << " | " << right->getAnchor() << std::endl;
00201             rval = false;
00202         }
00203         
00204         std::vector<string> leftPorts;
00205         std::vector<string> rightPorts;
00206         std::vector<string>::iterator leftport;
00207         std::vector<string>::iterator rightport;
00208         for (PortSharedPtrConstIterator leftport = left->portsBegin(); 
00209             leftport != left->portsEnd(); leftport++) {
00210             string t = (*leftport)->getInstancePtr().lock()->getName();
00211             t.append(".");
00212             t.append((*leftport)->getPinName());
00213             leftPorts.push_back(t);
00214         }
00215         for (PortSharedPtrConstIterator rightport = right->portsBegin(); 
00216             rightport != right->portsEnd(); rightport++) {
00217             string t = (*rightport)->getInstancePtr().lock()->getName();
00218             t.append(".");
00219             t.append((*rightport)->getPinName());
00220             rightPorts.push_back(t);
00221         }
00222         for (leftport = leftPorts.begin(); leftport != leftPorts.end(); leftport++) {
00223             bool found = false;
00224             for (rightport = rightPorts.begin(); rightport != rightPorts.end(); rightport++) {
00225                 if (*leftport == *rightport) {
00226                     found = true;
00227                     break;
00228                 }
00229             }
00230             if (found) {
00231                 rightPorts.erase(rightport);
00232             } else {
00233                 mStream << "< Module " << left->getName() << " port: "
00234                     << *leftport << std::endl;
00235                 rval = false;
00236             }
00237         }
00238         for (rightport = rightPorts.begin(); rightport != rightPorts.end(); rightport++) {
00239             mStream << "> Module " << right->getName() << " port: "
00240                 << *rightport << std::endl;
00241             rval = false;
00242         }
00243         leftPorts.clear();
00244         rightPorts.clear();
00245 
00246         // A module is a circuit
00247         rval = diffCircuit(left, right) && rval;
00248         return rval;
00249     }
00250     /// \brief Diff circuit pointers, recursively compare nets, instances and config map.
00251     bool diffCircuit(const CircuitSharedPtr& left, const CircuitSharedPtr& right) {
00252         bool rval = true;
00253         
00254         InstanceSharedPtrVector leftInstances;
00255         InstanceSharedPtrVector rightInstances;
00256         InstanceSharedPtrIterator ileft;
00257         InstanceSharedPtrIterator iright;
00258         
00259         for (ileft = left->instancesBegin(); ileft!= left->instancesEnd(); ileft++) {
00260             leftInstances.push_back(*ileft);
00261         }
00262         for (iright = right->instancesBegin(); iright!= right->instancesEnd(); iright++) {
00263             rightInstances.push_back(*iright);
00264         }
00265         for (ileft = leftInstances.begin(); ileft != leftInstances.end(); ileft++) {
00266             bool found = false;
00267             for (iright = rightInstances.begin(); iright != rightInstances.end(); iright++) {
00268                 if ((*ileft)->getName() == (*iright)->getName()) {
00269                     found = true;
00270                     break;
00271                 }
00272             }
00273             if (found) {
00274                 //mStream << "Instance " << (*ileft)->getName() << std::endl;
00275                 rval = diffInstance(*ileft, *iright) && rval;
00276                 rightInstances.erase(iright);
00277             } else {
00278                 mStream << "< Instance " << (*ileft)->getName() << std::endl;
00279                 rval = false;
00280             }
00281         }
00282         for (iright = rightInstances.begin(); iright != rightInstances.end(); iright++) {
00283             mStream << "> Instance " << (*iright)->getName() << std::endl;
00284             rval = false;
00285         }
00286         leftInstances.clear();
00287         rightInstances.clear();
00288         
00289         NetSharedPtrVector leftNets;
00290         NetSharedPtrVector rightNets;
00291         NetSharedPtrIterator nleft;
00292         NetSharedPtrIterator nright;
00293         
00294         for (nleft = left->netsBegin(); nleft!= left->netsEnd(); nleft++) {
00295             leftNets.push_back(*nleft);
00296         }
00297         for (nright = right->netsBegin(); nright!= right->netsEnd(); nright++) {
00298             rightNets.push_back(*nright);
00299         }
00300         for (nleft = leftNets.begin(); nleft != leftNets.end(); nleft++) {
00301             bool found = false;
00302             for (nright = rightNets.begin(); nright != rightNets.end(); nright++) {
00303                 if ((*nleft)->getName() == (*nright)->getName()) {
00304                     found = true;
00305                     break;
00306                 }
00307             }
00308             if (found) {
00309                 rval = diffNet(*nleft, *nright) && rval;
00310                 rightNets.erase(nright);
00311             } else {
00312                 mStream << "< Net " << (*nleft)->getName() << std::endl;
00313                 rval = false;
00314             }
00315         }
00316         for (nright = rightNets.begin(); nright != rightNets.end(); nright++) {
00317             mStream << "> Net " << (*nright)->getName() << std::endl;
00318             rval = false;
00319         }
00320         leftNets.clear();
00321         rightNets.clear();
00322         
00323         string circuitname = "Circuit ";
00324         circuitname.append(left->getName());
00325         // A circuit is a configmap.
00326         rval = diffConfigMap(left, right, circuitname) && rval;
00327         return rval;
00328     }
00329     /// \brief Diff configuration information, this is called from circuits, instances and nets.
00330     bool diffConfigMap(const ConfigMapSharedPtr& left, const ConfigMapSharedPtr& right, 
00331         const string& parentStr) {
00332         bool rval = true;
00333         
00334         std::vector<string> leftConfigs;
00335         std::vector<string> rightConfigs;
00336         std::vector<string>::iterator ileft;
00337         std::vector<string>::iterator iright;
00338         
00339         torc::physical::ConfigMap::const_iterator p = left->configBegin();
00340         torc::physical::ConfigMap::const_iterator e = left->configEnd();
00341         while (p != e) {
00342             const torc::physical::Config& config = p->second;
00343             string t = p->first;
00344             t.append(":");
00345             t.append(config.getName());
00346             t.append(":");
00347             t.append(config.getValue());
00348             leftConfigs.push_back(t);
00349             p++;
00350         }
00351         p = right->configBegin();
00352         e = right->configEnd();
00353         while (p != e) {
00354             const torc::physical::Config& config = p->second;
00355             string t = p->first;
00356             t.append(":");
00357             t.append(config.getName());
00358             t.append(":");
00359             t.append(config.getValue());
00360             rightConfigs.push_back(t);
00361             p++;
00362         }
00363         for (ileft = leftConfigs.begin(); ileft != leftConfigs.end(); ileft++) {
00364             bool found = false;
00365             for (iright = rightConfigs.begin(); iright != rightConfigs.end(); iright++) {
00366                 if (*ileft == *iright) {
00367                     found = true;
00368                     break;
00369                 }
00370             }
00371             if (found) {
00372                 //mStream << "Net " << (*nleft)->getName() << std::endl;
00373                 rightConfigs.erase(iright);
00374             } else {
00375                 mStream << "< " << parentStr << " Config " << *ileft << std::endl;
00376                 rval = false;
00377             }
00378         }
00379         for (iright = rightConfigs.begin(); iright != rightConfigs.end(); iright++) {
00380             mStream << "> " << parentStr << " Config " << *iright << std::endl;
00381             rval = false;
00382         }
00383         leftConfigs.clear();
00384         rightConfigs.clear();
00385         return rval;
00386     }
00387     /// \brief Diff instance pointers and then the underlying config map
00388     bool diffInstance(const InstanceSharedPtr& left, const InstanceSharedPtr& right) {
00389         bool rval = true;
00390         if (!(left->getType() == right->getType())) {
00391             mStream << "! Instance " << left->getName() << " type: " << left->getType() 
00392                 << " | " << right->getType() << std::endl;
00393             rval = false;
00394         }
00395         if (!(left->getTile() == right->getTile())) {
00396             mStream << "! Instance " << left->getName() << " tile: " << left->getTile() 
00397                 << " | " << right->getTile() << std::endl;;
00398             rval = false;
00399         }
00400         if (!(left->getSite() == right->getSite())) {
00401             mStream << "! Instance " << left->getName() << "site: " << left->getSite() 
00402                 << " | " << right->getSite() << std::endl;
00403             rval = false;
00404         }
00405         if (!(left->getBonding() == right->getBonding())) {
00406             mStream << "! Instance " << left->getName() << " bonding: " << left->getBonding() 
00407                 << " | " << right->getBonding() << std::endl;
00408             rval = false;
00409         }
00410 
00411         string instancename = "Instance ";
00412         instancename.append(left->getName());
00413         // An instance is a configmap.
00414         rval = diffConfigMap(left, right, instancename) && rval;
00415         return rval;
00416     }
00417     /// \brief Diff net pointers and then the underlying config map.
00418     bool diffNet(const NetSharedPtr& left, const NetSharedPtr& right) {
00419         bool rval = true;
00420         if (!(left->getNetType() == right->getNetType())) {
00421             mStream << "! Net " << left->getName() << " type: " << left->getNetType()
00422                 << " | " << right->getNetType() << std::endl;
00423             rval = false;
00424         }
00425         
00426         std::vector<string> leftPins;
00427         std::vector<string> rightPins;
00428         std::vector<string>::iterator leftpin;
00429         std::vector<string>::iterator rightpin;
00430         
00431         for (InstancePinSharedPtrConstIterator leftpinPtr = left->sourcesBegin(); 
00432             leftpinPtr != left->sourcesEnd(); leftpinPtr++) {
00433             string t = (*leftpinPtr)->getInstancePtr().lock()->getName();
00434             t.append(".");
00435             t.append((*leftpinPtr)->getPinName());
00436             leftPins.push_back(t);
00437         }
00438         for (InstancePinSharedPtrConstIterator rightpinPtr = right->sourcesBegin(); 
00439             rightpinPtr != right->sourcesEnd(); rightpinPtr++) {
00440             string t = (*rightpinPtr)->getInstancePtr().lock()->getName();
00441             t.append(".");
00442             t.append((*rightpinPtr)->getPinName());
00443             rightPins.push_back(t);
00444         }
00445         for (leftpin = leftPins.begin(); leftpin != leftPins.end(); leftpin++) {
00446             bool found = false;
00447             for (rightpin = rightPins.begin(); rightpin != rightPins.end(); rightpin++) {
00448                 if (*leftpin == *rightpin) {
00449                     found = true;
00450                     break;
00451                 }
00452             }
00453             if (found) {
00454                 rightPins.erase(rightpin);
00455             } else {
00456                 mStream << "< Net " << left->getName() << " outpin: "
00457                     << *leftpin << std::endl;
00458                 rval = false;
00459             }
00460         }
00461         for (rightpin = rightPins.begin(); rightpin != rightPins.end(); rightpin++) {
00462             mStream << "> Net " << right->getName() << " outpin: "
00463                 << *rightpin << std::endl;
00464             rval = false;
00465         }
00466         leftPins.clear();
00467         rightPins.clear();
00468         
00469         for (InstancePinSharedPtrConstIterator leftpinPtr = left->sinksBegin(); 
00470             leftpinPtr != left->sinksEnd(); leftpinPtr++) {
00471             string t = (*leftpinPtr)->getInstancePtr().lock()->getName();
00472             t.append(".");
00473             t.append((*leftpinPtr)->getPinName());
00474             leftPins.push_back(t);
00475         }
00476         for (InstancePinSharedPtrConstIterator rightpinPtr = right->sinksBegin(); 
00477             rightpinPtr != right->sinksEnd(); rightpinPtr++) {
00478             string t = (*rightpinPtr)->getInstancePtr().lock()->getName();
00479             t.append(".");
00480             t.append((*rightpinPtr)->getPinName());
00481             rightPins.push_back(t);
00482         }
00483         for (leftpin = leftPins.begin(); leftpin != leftPins.end(); leftpin++) {
00484             bool found = false;
00485             for (rightpin = rightPins.begin(); rightpin != rightPins.end(); rightpin++) {
00486                 if (*leftpin == *rightpin) {
00487                     found = true;
00488                     break;
00489                 }
00490             }
00491             if (found) {
00492                 rightPins.erase(rightpin);
00493             } else {
00494                 mStream << "< Net " << left->getName() << " inpin: "
00495                     << *leftpin << std::endl;
00496                 rval = false;
00497             }
00498         }
00499         for (rightpin = rightPins.begin(); rightpin != rightPins.end(); rightpin++) {
00500             mStream << "> Net " << right->getName() << " inpin: "
00501                 << *rightpin << std::endl;
00502             rval = false;
00503         }
00504         leftPins.clear();
00505         rightPins.clear();
00506         
00507         std::vector<string> leftPips;
00508         std::vector<string> rightPips;
00509         std::vector<string>::iterator leftpip;
00510         std::vector<string>::iterator rightpip;
00511         for (PipConstIterator leftpip = left->pipsBegin(); 
00512             leftpip != left->pipsEnd(); leftpip++) {
00513             string t = leftpip->getTileName();
00514             t.append(" ");
00515             t.append(leftpip->getSourceWireName());
00516             t.append(" ");
00517             t.append(leftpip->getDirectionString());
00518             t.append(" ");
00519             t.append(leftpip->getSinkWireName());
00520             leftPips.push_back(t);
00521         }
00522         for (PipConstIterator rightpip = right->pipsBegin(); 
00523             rightpip != right->pipsEnd(); rightpip++) {
00524             string t = rightpip->getTileName();
00525             t.append(" ");
00526             t.append(rightpip->getSourceWireName());
00527             t.append(" ");
00528             t.append(rightpip->getDirectionString());
00529             t.append(" ");
00530             t.append(rightpip->getSinkWireName());
00531             rightPips.push_back(t);
00532         }
00533         for (leftpip = leftPips.begin(); leftpip != leftPips.end(); leftpip++) {
00534             bool found = false;
00535             for (rightpip = rightPips.begin(); rightpip != rightPips.end(); rightpip++) {
00536                 if (*leftpip == *rightpip) {
00537                     found = true;
00538                     break;
00539                 }
00540             }
00541             if (found) {
00542                 rightPips.erase(rightpip);
00543             } else {
00544                 mStream << "< Net " << left->getName() << " pip: "
00545                     << *leftpip << std::endl;
00546                 rval = false;
00547             }
00548         }
00549         for (rightpip = rightPips.begin(); rightpip != rightPips.end(); rightpip++) {
00550             mStream << "> Net " << right->getName() << " pip: "
00551                 << *rightpip << std::endl;
00552             rval = false;
00553         }
00554         leftPips.clear();
00555         rightPips.clear();
00556         
00557         string netname = "Net ";
00558         netname.append(left->getName());
00559         // A net is a configmap.
00560         rval = diffConfigMap(left, right, netname) && rval;
00561         return rval;
00562     }
00563 
00564 };
00565 
00566 } // namespace torc
00567 
00568 #endif // TORC_UTILS_PHYSICALDIFF_HPP