PKIFReversiblePathBuilder.cpp

Go to the documentation of this file.

#include "ASN1Helper.h"
#include "BasicChecksUtils.h"
#include "BasicConstraints.h"
#include "BuilderStatistics.h"
#include "BuilderUtils.h"
#include "Certificate.h"
#include "GottaMatch.h"
#include "Name.h"
#include "PathResults.h"
#include "IPKIFCertRepository.h"
#include "IPKIFCertRepositoryUpdate.h"
#include "IPKIFTrustCache.h"
#include "IPKIFCRLRepository.h"
#include "IPKIFNameAndKey.h"
#include "IPKIFSupportsSynonymousSources.h"
#include "IssuedBy.h"
#include "NodeInNodeList.h"
#include "PKIFCertificateNodeEntry.h"
#include "PKIFCertificatePath.h"
#include "PKIFCertStatus.h"
#include "PKIFErrors.h"
#include "PKIFMediators.h"
#include "PKIFNameAndKeyWithScore.h"
#include "PKIFPathException.h"
#include "PKIFPathLogger.h"
#include "PKIFPathSettings.h"
#include "PKIFReversiblePathBuilder.h"
#include "PKIFReversePathState.h"
#include "PKIFTrustRoot.h"
#include "PKIX1Explicit88.h"
#include "ToolkitUtils.h"
#include <sstream>
#include "PKIFDefaultScoring.h"

#include "boost/numeric/conversion/cast.hpp"

using boost::numeric_cast;
using boost::bad_numeric_cast;


#include <iterator>

using namespace std;
using namespace boost;

void RemoveNotIssuedTo(CPKIFNamePtr& name, CPKIFCertificateNodeList& certList)
{
    NotIssuedTo notIssuedTo;
    notIssuedTo.SetRHS(name);
    CPKIFCertificateNodeList::iterator end;
    end = remove_if(certList.begin(), certList.end(), notIssuedTo);
    certList.erase(end, certList.end());
}
void RemoveNotIssuedBy(CPKIFNamePtr& name, CPKIFCertificateNodeList& certList)
{
    NotIssuedBy notIssuedBy;
    notIssuedBy.SetRHS(name);
    CPKIFCertificateNodeList::iterator end;
    end = remove_if(certList.begin(), certList.end(), notIssuedBy);
    certList.erase(end, certList.end());
}

//defined in Name.cpp
bool RDNsMatch(
    CACX509V3RelativeDistinguishedName* lhs,
    CACX509V3RelativeDistinguishedName* rhs);


class NameAndKeyNodeMatch
{
public:
    bool operator()(const CPKIFNameAndKeyWithScorePtr& t);

    void SetRHS(const IPKIFNameAndKeyPtr& rhs) {m_rhs = rhs;}
private:
    IPKIFNameAndKeyPtr m_rhs;
};

bool NameAndKeyNodeMatch::operator()(const CPKIFNameAndKeyWithScorePtr& t)
{
    return *t == *m_rhs;        
}

#define NAME_MATCHES_TARGET_ISSUER          5000
#define ISSUED_BY_TRUST_ROOT                5000
#define ISSUED_BY_CERT_IN_CACHE             500
#define BASIC_CONSTRAINTS_PRESENT_AND_SET   75
#define VAL_PERIOD_OK                       75
#define ALGS_MATCH                          100
#define KEY_IDS_MATCH                       6000 
#define NOT_SELF_ISSUED                     50
#define NOT_SELF_SIGNED                     50

//added the following - 7/21/2005
#define HAS_AT_ONE_POLICY                   25
#define MATCH_POLICY_WITH_PREV_CERT         25
#define MATCH_POLICY_WITH_SETTINGS          25

bool scoreCompare(
    const CPKIFNameAndKeyWithScorePtr& lhs, 
    const CPKIFNameAndKeyWithScorePtr& rhs)
{
    LOG_STRING_DEBUG("scoreCompare(const CPKIFCertificateNodeEntryPtr& lhs, const CPKIFCertificateNodeEntryPtr& rhs)", TOOLKIT_PATH_MISC, 0, NULL);

    int rhsScore = rhs->GetScore();
    int lhsScore = lhs->GetScore();
    return lhsScore > rhsScore;
}

int GetNumMatchingRdns(CPKIFNamePtr& name1, CPKIFNamePtr& name2)
{
    CACASNWRAPPER_CREATE(CACX509V3Name, objPDU1);
    CPKIFBufferPtr name1Buf = name1->rawName();
    objPDU1.Decode(name1Buf->GetBuffer(), name1Buf->GetLength());
    
    CACASNWRAPPER_CREATE(CACX509V3Name, objPDU2);
    CPKIFBufferPtr name2Buf = name2->rawName();
    objPDU2.Decode(name2Buf->GetBuffer(), name2Buf->GetLength());


    DListNode* curLHS = objPDU1->u.rdnSequence->head;
    DListNode* curRHS = objPDU2->u.rdnSequence->head;
    unsigned int max = 0;
    if(objPDU1->u.rdnSequence->count > objPDU2->u.rdnSequence->count)
        max = objPDU2->u.rdnSequence->count;
    else
        max = objPDU1->u.rdnSequence->count;

    for(unsigned int ii = 0; ii < max; ++ii)
    {
        //added 8/26/2004
        ASN1OpenType* lhsP = (ASN1OpenType*)curLHS->data;
        ASN1OpenType* rhsP = (ASN1OpenType*)curRHS->data;
        if(lhsP->numocts != rhsP->numocts || 0 != memcmp(lhsP->data, rhsP->data, rhsP->numocts))
        {
            //parse and compare if binary equality fails - 8/26/2004
            CACASNWRAPPER_CREATE(CACX509V3RelativeDistinguishedName, tmpPDULHS);
            CACX509V3RelativeDistinguishedName* lhs = tmpPDULHS.Decode(*lhsP);

            CACASNWRAPPER_CREATE(CACX509V3RelativeDistinguishedName, tmpPDURHS);
            CACX509V3RelativeDistinguishedName* rhs = tmpPDURHS.Decode(*rhsP);

            if(!RDNsMatch(lhs, rhs))
                return ii;
        }
        curLHS = curLHS->next; 
        curRHS = curRHS->next;
    }
    return max;
}

void ScoreAndSortNodes(
    CPKIFNameAndKeyWithScoreListPtr& listToSort, 
    CPKIFCertificatePtr& targetCert, 
    IPKIFNameAndKeyPtr& issuerNameAndKey, 
    CPKIFPathSettingsPtr& settings, 
    bool toToSortContainsTrustAnchors)
{
    CPKIFNamePtr targetIssuerName = targetCert->Issuer();
    CPKIFPolicyInformationListPtr initPolSet;
    settings->GetInitialPolicySet(initPolSet);

    CPKIFNamePtr curCertIssuerName;
    if(issuerNameAndKey != (IPKIFNameAndKey*)NULL)
        curCertIssuerName = issuerNameAndKey->GetSubjectName();

    CPKIFNameAndKeyWithScoreList::iterator pos;
    CPKIFNameAndKeyWithScoreList::iterator end = listToSort->end();
    for(pos = listToSort->begin(); pos != end; ++pos)
    {
        (*pos)->ClearScore();
        IPKIFNameAndKeyPtr curNameAndKey = (*pos)->GetNameAndKey();

        //if subject name matches target issuer name
        if(*targetIssuerName == *curNameAndKey->GetSubjectName())
            (*pos)->AddToScore(NAME_MATCHES_TARGET_ISSUER);


        CPKIFNamePtr tmpName = curNameAndKey->GetSubjectName();
        int namePoints = 1000 * GetNumMatchingRdns(targetIssuerName, tmpName);
        (*pos)->AddToScore(namePoints);

        if(curCertIssuerName != (CPKIFName*)NULL && !(*curCertIssuerName == *curNameAndKey->GetIssuerName()))
        {
            (*pos)->ClearScore();
            continue;   //no point further evaluating something for which name chaining fails
        }

        //some checks are only appropriate if the item is a certificate
        CPKIFCertificatePtr curCert = dynamic_pointer_cast<CPKIFCertificate, IPKIFNameAndKey>(curNameAndKey);
        if(curCert != (CPKIFCertificate*)NULL)
        {
            CPKIFBasicConstraintsPtr basicConstraints = curCert->GetExtension<CPKIFBasicConstraints>();
            bool isCA = false;
            if(basicConstraints != (CPKIFBasicConstraints*)NULL)
            {
                if(basicConstraints->isCA())
                    (*pos)->AddToScore(BASIC_CONSTRAINTS_PRESENT_AND_SET);
                else
                {
                    (*pos)->ClearScore();
                    continue;
                }
            }       

            //XXX***add more sorting logic here (steal from forward builder
        }
    }

    sort(listToSort->begin(), listToSort->end(), scoreCompare);

#ifdef _DEBUG
    IPKIFNameAndKeyPtr frontNK = listToSort->front()->GetNameAndKey();
    int score = listToSort->front()->GetScore();
    CPKIFNamePtr frontNKName = frontNK->GetSubjectName();
    const char* frontNKNameStr = frontNKName->ToString();
#endif
}

struct CPKIFReversiblePathBuilderImpl 
{
    PathBuildingDirection m_pbd;
    CPKIFReversiblePathBuilder *m_parent;
    std::vector<CPKIFNameAndKeyWithScoreList> m_previouslyTriedPaths;
    bool TriedBefore(CPKIFNameAndKeyWithScoreList& builtPathNK);

    //function that builds a table or grows a table by extending rows with additional sources
    bool BuildOrGrowTable(CPKIFReversePathStatePtr& reverseState);

    //function that checks for paths in the current table of certs
    bool CheckAlternatives(CPKIFCertificatePath& path, CPKIFReversePathStatePtr& reverseState);

    //function that removes the current row nearest the root
    void PuntTopRow(CPKIFReversePathStatePtr& reverseState);

    bool GrowRows(CPKIFReversePathStatePtr& reverseState);

    //function that removes certs from a list that would create a loop in the current path
    void RemoveLoopMakers(CPKIFCertificateNodeList& certList, CPKIFReversePathStatePtr& reverseState);

    void PrepareState_Forward(CPKIFReversePathStatePtr& reverseState, CPKIFCertificatePath& path);
    void PrepareState_Reverse(CPKIFReversePathStatePtr& reverseState, CPKIFCertificatePath& path);
    void CreateState(CPKIFCertificatePath& path, PathBuildingDirection pbd);
    void CheckInputs(CPKIFCertificatePath& path);
    bool TargetIsTrustAnchor(CPKIFCertificatePtr& cert);
    IPKIFNameAndKeyPtr GetCurrentCert(CPKIFReversePathStatePtr& reverseState);

    void GetCerts(CPKIFCertificateSourceListPtr& curSourceList, CPKIFCertificateNodeList& certNodeList, CPKIFReversePathStatePtr& reverseState);
    void SortAndSaveLists(CPKIFReversePathStatePtr& reverseState, CPKIFNameAndKeyWithScoreListPtr& newList, CPKIFCertificateSourceListPtr& sources);
    void RemoveExtraneous(CPKIFCertificateNodeList& certList, CPKIFReversePathStatePtr& reverseState);
};

void CPKIFReversiblePathBuilderImpl::SortAndSaveLists(CPKIFReversePathStatePtr& reverseState, 
                                                  CPKIFNameAndKeyWithScoreListPtr& newList, CPKIFCertificateSourceListPtr& sources)
{
    //sort sources

    //first off, get some cert from sources if newList is empty
    if(newList->empty())
    {
        CPKIFCertificateNodeList certNodeList;
        GetCerts(sources, certNodeList, reverseState);

        //remove any loops from the list, if there is a list
        RemoveLoopMakers(certNodeList, reverseState);
        RemoveExtraneous(certNodeList, reverseState);

        if(!certNodeList.empty())
        {
            //if there are still certs in the list, then add them to the corresponding row
            //in m_table, provided the cert is not already in the list

            CPKIFCertificateNodeList::iterator cnlPos;
            CPKIFCertificateNodeList::iterator cnlEnd = certNodeList.end();
            for(cnlPos = certNodeList.begin(); cnlPos != cnlEnd; ++cnlPos)
            {
                IPKIFNameAndKeyPtr cnlCertAsNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, CPKIFCertificate>((*cnlPos)->GetCert());
                CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(cnlCertAsNameAndKey));
                newList->push_back(newNode);
            }
        }
    }

    //if we don't have any certs, simply return and let PuntTopRow take over
    if(newList->empty())
        return;

    if(PBD_FORWARD == reverseState->m_direction)
    {
        //TODO: 
        //  - sort the name and key list for forward direction building
        IPKIFTrustCache* iTrust = m_parent->GetMediatorFromParent<IPKIFTrustCache>();
        IPKIFCertRepository* iCert = m_parent->GetMediatorFromParent<IPKIFCertRepository>();
        IPKIFNameAndKeyPtr curCertAsNameAndKey = GetCurrentCert(reverseState);
        CPKIFCertificatePtr curCert = dynamic_pointer_cast<CPKIFCertificate, IPKIFNameAndKey>(curCertAsNameAndKey);

        CPKIFDefaultScoring s;
        int nCAsBelow = 0;
        try {
            nCAsBelow = boost::numeric_cast<int,size_t>(reverseState->m_table.size() - 1);
        }catch(std::exception &e){
            RAISE_PATH_EXCEPTION(e.what(), m_parent->thisComponent, COMMON_INVALID_INPUT, this)
        }
        s.ScoreAndSortNodes(newList, curCert, reverseState->m_pathSettings, iTrust, nCAsBelow ,iCert);
        
        reverseState->m_table.push_back(newList);
        reverseState->m_sourceTable.push_back(sources);

#ifdef _DEBUG
        vector<string> v;
        vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzpos;
        vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzend = reverseState->m_table.end();
        for(zzzpos = reverseState->m_table.begin(); zzzpos != zzzend; ++zzzpos)
        {
            v.push_back((*zzzpos)->front()->GetNameAndKey()->GetSubjectName()->ToString());
            v.push_back((*zzzpos)->front()->GetNameAndKey()->GetIssuerName()->ToString());
        }
#endif
    }
    else
    {
        //TODO: 
        //  - sort the name and key list for reverse direction building
        reverseState->m_table.insert(reverseState->m_table.begin(), newList);
        reverseState->m_sourceTable.insert(reverseState->m_sourceTable.begin(), sources);
    }
}

bool CPKIFReversiblePathBuilderImpl::TargetIsTrustAnchor(CPKIFCertificatePtr& cert)
{
    IPKIFTrustCache* iTrust = m_parent->GetMediatorFromParent<IPKIFTrustCache>();

    IPKIFTrustAnchorList tmpRootList;
    iTrust->GetTrustRoots(cert->GetSubjectName(), tmpRootList);
    if(!tmpRootList.empty())
    {
        //iterate over the roots and see if any match the target
        IPKIFTrustAnchorList::iterator rootPos;
        IPKIFTrustAnchorList::iterator rootEnd = tmpRootList.end();
        for(rootPos = tmpRootList.begin(); rootPos != rootEnd; ++rootPos)
        {
            IPKIFNameAndKeyPtr taNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, IPKIFTrustAnchor>(*rootPos);
            IPKIFNameAndKeyPtr certNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, CPKIFCertificate>(cert);
            if(*certNameAndKey == *taNameAndKey)
                return true;
        }
    }

    return false;
}

void CPKIFReversiblePathBuilderImpl::PrepareState_Forward(CPKIFReversePathStatePtr& reverseState, CPKIFCertificatePath& path)
{
    reverseState->m_direction = PBD_FORWARD;

    IPKIFNameAndKeyPtr targetCertAsNameAndKey;
    CPKIFCertificatePtr targetCert;
    path.GetTarget(targetCert);
    targetCertAsNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, CPKIFCertificate>(targetCert);

    reverseState->m_targetCert = targetCert;
    reverseState->m_targetCertAsNameAndKey = targetCertAsNameAndKey;

    CPKIFCertificateSourceListPtr emptySourceList(new CPKIFCertificateSourceList);
    CPKIFNameAndKeyWithScoreListPtr newList(new CPKIFNameAndKeyWithScoreList);
    CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(reverseState->m_targetCertAsNameAndKey));
    newList->push_back(newNode);

    reverseState->m_table.push_back(newList);
    reverseState->m_sourceTable.push_back(emptySourceList);

#ifdef _DEBUG
    vector<string> v;
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzpos;
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzend = reverseState->m_table.end();
    for(zzzpos = reverseState->m_table.begin(); zzzpos != zzzend; ++zzzpos)
    {
        v.push_back((*zzzpos)->front()->GetNameAndKey()->GetSubjectName()->ToString());
        v.push_back((*zzzpos)->front()->GetNameAndKey()->GetIssuerName()->ToString());
    }
#endif
}

void CPKIFReversiblePathBuilderImpl::PrepareState_Reverse(CPKIFReversePathStatePtr& reverseState, CPKIFCertificatePath& path)
{
    reverseState->m_direction = PBD_REVERSE;

    //get the target certificate and save a pointer to it and to its IPKIFNameAndKey interface in reverseState
    IPKIFNameAndKeyPtr targetCertAsNameAndKey;
    CPKIFCertificatePtr targetCert;
    path.GetTarget(targetCert);
    targetCertAsNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, CPKIFCertificate>(targetCert);

    reverseState->m_targetCert = targetCert;
    reverseState->m_targetCertAsNameAndKey = targetCertAsNameAndKey;

    //since we are building in reverse, we will get a list of all trust anchors.  
    CPKIFNamePtr emptyName;
    IPKIFTrustAnchorList tl;
    IPKIFTrustCache* iTrust = m_parent->GetMediatorFromParent<IPKIFTrustCache>();
    iTrust->GetTrustRoots(emptyName, tl);

    //create a CPKIFNameAndKeyWithScoreList and push the trust anchors into it.  then sort the list
    //and push it into the table.
    CPKIFNameAndKeyWithScoreListPtr scoreList(new CPKIFNameAndKeyWithScoreList);    

    IPKIFTrustAnchorList::iterator pos;
    IPKIFTrustAnchorList::iterator end = tl.end();
    for(pos = tl.begin(); pos != end; ++pos)
    {
        IPKIFNameAndKeyPtr curTA = dynamic_pointer_cast<IPKIFNameAndKey, IPKIFTrustAnchor>(*pos);

        CPKIFNameAndKeyWithScorePtr tmp(new CPKIFNameAndKeyWithScore(curTA));
        scoreList->push_back(tmp);
    }

    IPKIFNameAndKeyPtr emptyNameAndKey;
    ScoreAndSortNodes(scoreList, targetCert, emptyNameAndKey, reverseState->m_pathSettings, true);

    //there is not a node for additional root sources, so we simply push an empty row there
    CPKIFCertificateSourceListPtr sourceList(new CPKIFCertificateSourceList); //NULL indicates time to remove, need empty list

    reverseState->m_table.push_back(scoreList);
    reverseState->m_sourceTable.push_back(sourceList);
}

void CPKIFReversiblePathBuilderImpl::CreateState(CPKIFCertificatePath& path, PathBuildingDirection pbd)
{
    //allocate the new state... (throw bad_alloc)
    CPKIFReversePathStatePtr reverseState(new CPKIFReversePathState);   

    reverseState->m_sources = LOCAL;
    reverseState->m_bTableIsComplete = false;
    reverseState->m_bBuildStarted = false;

    //and builder statistics (throw bad_alloc)
    CPKIFBuilderStatisticsPtr bs(new CPKIFBuilderStatistics);
    path.SetBuilderStats(bs);

    //store it in the path
    CPKIFCertificatePathStatePtr tmpState(reverseState);
    path.SetState(tmpState);

    path.GetPathSettings(reverseState->m_pathSettings);

    if(PBD_FORWARD == pbd)
        PrepareState_Forward(reverseState, path);
    else
        PrepareState_Reverse(reverseState, path);
}


void CPKIFReversiblePathBuilderImpl::CheckInputs(CPKIFCertificatePath& path)
{
    LOG_STRING_DEBUG("CPKIFReversiblePathBuilder::CreateInputs(CPKIFCertificatePath& path)", m_parent->thisComponent, 0, this);

    //we need to have at least an IPKIFTrustCache interface and an IPKIFCertRepository interface
    IPKIFTrustCache* iTrust = m_parent->GetMediatorFromParent<IPKIFTrustCache>();
    if(NULL == iTrust)
        RAISE_PATH_EXCEPTION("IPKIFTrustCache interface not available.", m_parent->thisComponent, COMMON_MEDIATOR_MISSING, this)

    IPKIFCertRepository* iCert = m_parent->GetMediatorFromParent<IPKIFCertRepository>();
    if(NULL == iCert)
        RAISE_PATH_EXCEPTION("IPKIFCertRepository interface not available.", m_parent->thisComponent, COMMON_MEDIATOR_MISSING, this)

    //require that settings be non-NULL
    CPKIFPathSettingsPtr settings;
    path.GetPathSettings(settings);
    if(settings == (CPKIFPathSettings*)NULL)
        RAISE_PATH_EXCEPTION("Path parameter contained NULL path settings.", m_parent->thisComponent, COMMON_INVALID_INPUT, this)

    CPKIFCertificatePtr curCert;
    path.GetTarget(curCert);
    if(curCert == (CPKIFCertificate*)NULL)
        RAISE_PATH_EXCEPTION("The path parameter did not specify a target certificate.", m_parent->thisComponent, COMMON_INVALID_INPUT, this)
}

size_t GetTableSize(vector<CPKIFNameAndKeyWithScoreListPtr>& v)
{
    size_t rowSum = 0;
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator pos;
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator end = v.end();
    for(pos = v.begin(); pos != end; ++pos)
        rowSum += (*pos)->size();

    return rowSum;
}

void CPKIFReversiblePathBuilderImpl::GetCerts(CPKIFCertificateSourceListPtr& curSourceList, CPKIFCertificateNodeList& certNodeList, CPKIFReversePathStatePtr& reverseState)
{
    do
    {
        //get the source at the back of the source list, then remove it from the list
        CPKIFCertificateSourcePtr curSource = curSourceList->back();
        curSourceList->pop_back();

        //retrieve some certs, if possible
        curSource->GetCertificates(certNodeList, reverseState->m_direction);

        //loop until we either get some certs or run out of sources in this row
    }while(certNodeList.empty() && !curSourceList->empty());

#ifdef _DEBUG
    vector<string> v;
    CPKIFCertificateNodeList::iterator pos;
    CPKIFCertificateNodeList::iterator end = certNodeList.end();
    for(pos = certNodeList.begin(); pos != end; ++pos)
    {
        v.push_back((*pos)->GetCert()->Subject()->ToString());
        v.push_back((*pos)->GetCert()->Issuer()->ToString());
    }
#endif
}

bool CPKIFReversiblePathBuilderImpl::GrowRows(CPKIFReversePathStatePtr& reverseState)
{
    bool rv = false;
    int numRows = 0;
    try 
    {
        numRows = numeric_cast<int>(reverseState->m_table.size());
    }
    catch(bad_numeric_cast &) 
    {
        throw CPKIFException(TOOLKIT_PATH, COMMON_INVALID_INPUT, "Table size is an impossibly long number.");
    }
    
    assert((reverseState->m_table.empty() &&reverseState->m_sourceTable.empty()) || (reverseState->m_table.size() == reverseState->m_sourceTable.size()));

    int ii = PBD_FORWARD == reverseState->m_direction? numRows-2 : 0;
    int terminator = PBD_FORWARD == reverseState->m_direction? 0 : numRows-2;
    if(ii < 0 || terminator < 0)
    {
        ii = 0; terminator = 0 ; //this is necessary when only row is root row
    }
    for(; (PBD_FORWARD == reverseState->m_direction && ii >= terminator) || (PBD_REVERSE == reverseState->m_direction && ii <= terminator); 
        PBD_FORWARD == reverseState->m_direction? --ii : ++ii)
    {
        CPKIFNameAndKeyWithScoreListPtr curNameAndKeyList = reverseState->m_table[ii];
        CPKIFCertificateSourceListPtr curSourceList = reverseState->m_sourceTable[ii];
        if(curSourceList == (CPKIFCertificateSourceList*)NULL || curSourceList->empty())
            continue;

        CPKIFCertificateNodeList certNodeList;
        GetCerts(curSourceList, certNodeList, reverseState);

        //remove any loops from the list, if there is a list
        RemoveLoopMakers(certNodeList, reverseState);
        RemoveExtraneous(certNodeList, reverseState);

        if(!certNodeList.empty())
        {
            //if there are still certs in the list, then add them to the corresponding row
            //in m_table, provided the cert is not already in the list

            CPKIFCertificateNodeList::iterator cnlPos;
            CPKIFCertificateNodeList::iterator cnlEnd = certNodeList.end();
            for(cnlPos = certNodeList.begin(); cnlPos != cnlEnd; ++cnlPos)
            {
                IPKIFNameAndKeyPtr cnlCertAsNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, CPKIFCertificate>((*cnlPos)->GetCert());
                CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(cnlCertAsNameAndKey));
                GottaMatch<CPKIFNameAndKeyWithScorePtr> gm;
                gm.SetRHS(newNode);
                if(curNameAndKeyList->end() == find_if(curNameAndKeyList->begin(), curNameAndKeyList->end(), gm))
                {
                    curNameAndKeyList->push_back(newNode);
                    rv = true;
                }
            }
        }

        if(curSourceList->empty() && curNameAndKeyList->empty())
        {
            CPKIFCertificateSourceListPtr emptyList;
            reverseState->m_sourceTable[ii] = emptyList;
        }
    }

    return rv;
}

void CPKIFReversiblePathBuilderImpl::PuntTopRow(
    CPKIFReversePathStatePtr& reverseState)

{
#ifdef _DEBUG
            vector<string> v;
            vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzpos;
            vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzend = reverseState->m_table.end();
            for(zzzpos = reverseState->m_table.begin(); zzzpos != zzzend; ++zzzpos)
            {
                v.push_back((*zzzpos)->front()->GetNameAndKey()->GetSubjectName()->ToString());
                v.push_back((*zzzpos)->front()->GetNameAndKey()->GetIssuerName()->ToString());
            }
#endif

    CPKIFNamePtr nameOfIssuerToDiscard;

    //We only care if GrowRow changes the current cert.  If it doesn't,
    //then we are still removing this row
    IPKIFNameAndKeyPtr preGrowCur = GetCurrentCert(reverseState);

    bool bAddedNewStuff = GrowRows(reverseState);

    IPKIFNameAndKeyPtr postGrowCur = GetCurrentCert(reverseState);
    if((preGrowCur == (IPKIFNameAndKey*)NULL && postGrowCur != (IPKIFNameAndKey*)NULL) || 
        ((preGrowCur != (IPKIFNameAndKey*)NULL && postGrowCur != (IPKIFNameAndKey*)NULL) && !(*preGrowCur == *postGrowCur)))
        return;

    if(PBD_FORWARD == reverseState->m_direction)
    {
        int size = 0;
        try 
        {
            size = numeric_cast<int>(reverseState->m_table.size());
        }
        catch(bad_numeric_cast &) 
        {
            throw CPKIFException(TOOLKIT_PATH, COMMON_INVALID_INPUT, "Table size is an impossibly long number.");
        }

        //the top of the table is the end of the vector - iterate in reverse
        vector<CPKIFNameAndKeyWithScoreListPtr>::reverse_iterator pos = reverseState->m_table.rbegin();
        vector<CPKIFNameAndKeyWithScoreListPtr>::reverse_iterator end = reverseState->m_table.rend();
        for(int ii = size - 1; pos != end - 1; ++pos, --ii) //end - 1 to avoid thwacking the target row
        {
            if((*pos)->empty())
                continue;

            //get the name of the issuer at the front of the current row
            if(nameOfIssuerToDiscard == (CPKIFName*)NULL)
                nameOfIssuerToDiscard = (*pos)->front()->GetNameAndKey()->GetIssuerName();

            CPKIFNamePtr tmpName = (*pos)->front()->GetNameAndKey()->GetSubjectName();

    #ifdef _DEBUG
            const char* curCertIssuerString = nameOfIssuerToDiscard->ToString();
            const char* curCertSubjectString = tmpName->ToString();
            size_t size = (*pos)->size();
    #endif

            RemoveAllIssuedBy(*pos, nameOfIssuerToDiscard);

    #ifdef _DEBUG
            size = (*pos)->size();
    #endif

            //update the previous name to the name of the front cert of the current row
            //it will be used to thin the next row if this row went empty on the above
            //remove call
            nameOfIssuerToDiscard = tmpName;

            //if the current row is not empty after the above remove call then there's still hope
            if(!(*pos)->empty())
                break;
            else
            {
                CPKIFCertificateSourceListPtr emptySourceList;
                reverseState->m_sourceTable[ii] = emptySourceList;
                reverseState->m_bTableIsComplete = false;
            }
        }
    }
    else
    {
        vector<CPKIFNameAndKeyWithScoreListPtr>::iterator pos = reverseState->m_table.begin();
        vector<CPKIFNameAndKeyWithScoreListPtr>::iterator end = reverseState->m_table.end();
        if(reverseState->m_bTableIsComplete)
        {
            (*pos)->clear();//remove target row
            ++pos;
        }

        int distanceLen = 0;
        try 
        {
            distanceLen = numeric_cast<int>(distance(reverseState->m_table.begin(), pos));
        }
        catch(bad_numeric_cast &) 
        {
            throw CPKIFException(TOOLKIT_PATH, COMMON_INVALID_INPUT, "Distance is an impossibly long number.");
        }


        for(int ii = distanceLen; pos != end; ++pos, ++ii)
        {
            if((*pos)->empty())
                continue;

            //get the name of the issuer at the front of the current row
            if(nameOfIssuerToDiscard == (CPKIFName*)NULL && pos != reverseState->m_table.begin())
                nameOfIssuerToDiscard = (*pos)->front()->GetNameAndKey()->GetSubjectName();
            else if(nameOfIssuerToDiscard == (CPKIFName*)NULL)
                nameOfIssuerToDiscard = (*pos)->front()->GetNameAndKey()->GetIssuerName();

            CPKIFNamePtr tmpName = (*pos)->front()->GetNameAndKey()->GetIssuerName();

    #ifdef _DEBUG
            const char* curCertIssuerString = nameOfIssuerToDiscard->ToString();
            const char* curCertSubjectString = tmpName->ToString();
            size_t size = (*pos)->size();
    #endif

            if(pos != reverseState->m_table.begin())
                RemoveAllIssuedTo(*pos, nameOfIssuerToDiscard);
            else
                RemoveAllIssuedBy(*pos, nameOfIssuerToDiscard);

    #ifdef _DEBUG
            size = (*pos)->size();
    #endif

            //update the previous name to the name of the front cert of the current row
            //it will be used to thin the next row if this row went empty on the above
            //remove call
            nameOfIssuerToDiscard = tmpName;

            //if the current row is not empty after the above remove call then there's still hope
            if(!(*pos)->empty())
                break;
            else
            {
                CPKIFCertificateSourceListPtr nullSourceList;
                reverseState->m_sourceTable[ii] = nullSourceList;
                reverseState->m_bTableIsComplete = false;
            }
        }
    }

    //state preservation (ideally, this would not be necessary as it indicates something else is wrong)
    {
        vector<CPKIFNameAndKeyWithScoreListPtr>::iterator nkPos;
        vector<CPKIFNameAndKeyWithScoreListPtr>::iterator nkEnd = reverseState->m_table.end();
        int ii = 0;
        CPKIFCertificateSourceListPtr nullSourceList;
        for(nkPos = reverseState->m_table.begin(); nkPos != nkEnd; ++nkPos, ++ii)
        {
            if((*nkPos)->empty())
                reverseState->m_sourceTable[ii] = nullSourceList;
        }
    }

    //look at each row in the table and delete those that are empty
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator newEnd = remove_if(reverseState->m_table.begin(), reverseState->m_table.end(), IsEmptyNameAndKey);
    reverseState->m_table.erase(newEnd, reverseState->m_table.end());

    vector<CPKIFCertificateSourceListPtr>::iterator newEndSourceList = remove_if(reverseState->m_sourceTable.begin(), reverseState->m_sourceTable.end(), IsNullCertificateSourceList);
    reverseState->m_sourceTable.erase(newEndSourceList, reverseState->m_sourceTable.end());
}

void CPKIFReversiblePathBuilderImpl::RemoveLoopMakers(
    CPKIFCertificateNodeList& certList, 
    CPKIFReversePathStatePtr& reverseState)
{
    //if the table is empty or certList is empty then there are no "loop makers" - return immediately
    if(reverseState->m_table.empty() || certList.empty())
        return;

    //otherwise - iterate over the table and build a partial path taking the frontmost
    //node from each row in the table (It'd be a good idea to maintain a running partial
    //path so we can avoid repeated calls to setup and tear down the partial path list)
    CPKIFNameAndKeyWithScoreList builtPath;
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator pos = reverseState->m_table.begin();
    vector<CPKIFNameAndKeyWithScoreListPtr>::iterator end = reverseState->m_table.end();
    for(; pos != end; ++pos)
    {
        if(!(*pos)->empty())    //should only ever occur on first row in cases where no locals existed but a remote did
        {
            IPKIFNameAndKeyPtr tmpNameAndKey = (*pos)->front()->GetNameAndKey();
            CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(tmpNameAndKey));
            builtPath.push_back(newNode);
        }
    }

#ifdef _DEBUG
    size_t size = certList.size();
#endif

    //prepare a NodeInNodeList predicate object with the partial path that was just built
    NodeInNodeList n;
    n.SetNodeList(&builtPath);

    //invoke the remove_if alg using the NodeInNodeList object (i.e. iterate over
    //certList and move all entries that are present in the builtPath to the end 
    //of the list so they can be removed by the call to erase).
    CPKIFCertificateNodeList::iterator newEnd = remove_if(certList.begin(), certList.end(), n);
    certList.erase(newEnd, certList.end());

#ifdef _DEBUG
    size = certList.size();
#endif
}

IPKIFNameAndKeyPtr CPKIFReversiblePathBuilderImpl::GetCurrentCert(CPKIFReversePathStatePtr& reverseState)
{
    IPKIFNameAndKeyPtr empty;
    if(reverseState->m_table.empty())
        return empty;

    if(PBD_FORWARD == reverseState->m_direction)
    {
        //building towards the trust anchor, so current focal point is the front of the list
        //at the back of the vector.
        if(reverseState->m_table.back()->empty())
            return empty;
        else
            return reverseState->m_table.back()->front()->GetNameAndKey();
    }
    else
    {
        //building towards the target, so current focal point is the front of the list at the
        //front of the vector.
        if(reverseState->m_table.front()->empty())
            return empty;
        else
            return reverseState->m_table.front()->front()->GetNameAndKey();
    }
}

bool IsSelfSigned(CPKIFCertificateNodeEntryPtr& certNode)
{
    if(certNode == (CPKIFCertificateNodeEntry*)NULL)
        return false;

    CPKIFCertificatePtr cert = certNode->GetCert();
    return cert->IsSelfSigned();
}

void CPKIFReversiblePathBuilderImpl::RemoveExtraneous(CPKIFCertificateNodeList& certList, CPKIFReversePathStatePtr& reverseState)
{
    if(certList.empty()) //nothing to do
        return;

    if(PBD_FORWARD == reverseState->m_direction)
    {
        CPKIFNamePtr tmpName = reverseState->m_table.back()->front()->GetNameAndKey()->GetIssuerName();
        RemoveNotIssuedTo(tmpName, certList);
    }
    else //PBD_REVERSE
    {
        //building from trust anchor to target, so the new list must feature certificates that were issued
        //by the current node from the table
        if(!reverseState->m_table.front()->empty())
        {
            CPKIFNamePtr tmpName = reverseState->m_table.front()->front()->GetNameAndKey()->GetSubjectName();
            RemoveNotIssuedBy(tmpName, certList);
        }
        //since this is not the root row, self-signed certs need not apply
        CPKIFCertificateNodeList::iterator end;
        end = remove_if(certList.begin(), certList.end(), IsSelfSigned);
        certList.erase(end, certList.end());

        //we do not need copies of certs in the list
        CPKIFCertificateNodeList listCopy;

        CPKIFCertificateNodeList::iterator clpos;
        CPKIFCertificateNodeList::iterator clend = certList.end();
        for(clpos = certList.begin(); clpos != clend; ++clpos)
        {
            GottaMatch<CPKIFCertificateNodeEntryPtr> gm;
            gm.SetRHS(*clpos);
            if(listCopy.end() == find_if(listCopy.begin(), listCopy.end(), gm))
                listCopy.push_back(*clpos);
        }

        certList.clear();
        copy(listCopy.begin(), listCopy.end(), back_inserter(certList));
    }
}

bool CPKIFReversiblePathBuilderImpl::BuildOrGrowTable(CPKIFReversePathStatePtr& reverseState)
{
    //if the table is complete and we are able to extend a few rows, we can return true
    //early and let CheckAlternatives have another go at it.
    if(reverseState->m_bTableIsComplete && GrowRows(reverseState))
        return true;
    else if(reverseState->m_bBuildStarted)
    {
        //get rid of a row and continue trying
        PuntTopRow(reverseState);
    }
    else
    {
        //Without this, the PuntTopRow above was eliminating a cert from the top row when 
        //building backwards.  Without the PuntTopRow, we never terminate.
        reverseState->m_bBuildStarted = true;
    }

    //----------------------------------------------------------------------------------------------------
    //  COLLECT INTERFACES
    //----------------------------------------------------------------------------------------------------
    //query for the various interfaces we will need:
    //  need: IPKIFCertRepository, IPKIFTrustCache
    //  use (if present): IPKIFCertRepositoryUpdate, IPKIFCRLRepository
    IPKIFCertRepository* iCert = m_parent->GetMediatorFromParent<IPKIFCertRepository>();
    IPKIFTrustCache* iTrust = m_parent->GetMediatorFromParent<IPKIFTrustCache>();
    if(NULL == iCert || NULL == iTrust)
        throw CPKIFPathException(m_parent->thisComponent, COMMON_MEDIATOR_MISSING, "IPKIFCertRepository and/or IPKIFTrustCache are not available.");

    //the cert and CRL update interfaces can be absent (if it's present we'll use it)
    IPKIFCertRepositoryUpdate* iCertUpdate = m_parent->GetMediatorFromParent<IPKIFCertRepositoryUpdate>();
    IPKIFCRLRepository* iCRL = m_parent->GetMediatorFromParent<IPKIFCRLRepository>();
    IPKIFSupportsSynonymousCertSources* iCertSS = m_parent->GetMediatorFromParent<IPKIFSupportsSynonymousCertSources>();

#ifdef _DEBUG
    const char* targetIssuerName = reverseState->m_targetCertAsNameAndKey->GetIssuerName()->ToString();
    const char* targetSubjectName = reverseState->m_targetCertAsNameAndKey->GetSubjectName()->ToString();
#endif

    IPKIFTrustAnchorList trustRootList; //used when building in the forward direction
    IPKIFNameAndKeyPtr curCertAsNameAndKey = GetCurrentCert(reverseState);
    
    do
    {
        size_t tableSize = reverseState->m_table.size();
        CPKIFCertificateSourceList certSourceList;
        CPKIFCertificateNodeList certList;

#ifdef _DEBUG
        const char* curCertIssuerString = curCertAsNameAndKey->GetIssuerName()->ToString();
        const char* curCertSubjectString = curCertAsNameAndKey->GetSubjectName()->ToString();
#endif

        //if building in the forward direction, we need to check to see if the issuer
        //is a trust anchor at each hop
        if(PBD_FORWARD == reverseState->m_direction && 
            iTrust->GetTrustRoots(curCertAsNameAndKey->GetIssuerName(), trustRootList))
        {
            //if we found a trust anchor, copy it into a CPKIFNameAndKeyWithScoreList and return true
            CPKIFNameAndKeyWithScoreListPtr newList(new CPKIFNameAndKeyWithScoreList);
            IPKIFTrustAnchorList::iterator trPos;
            IPKIFTrustAnchorList::iterator trEnd = trustRootList.end();
            for(trPos = trustRootList.begin(); trPos != trEnd; ++trPos)
            {
                IPKIFNameAndKeyPtr trPosAsNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, IPKIFTrustAnchor>(*trPos);
                CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(trPosAsNameAndKey));
                newList->push_back(newNode);
            }
            CPKIFCertificateSourceListPtr emptySourceList;
            reverseState->m_bTableIsComplete = true;

            reverseState->m_table.push_back(newList);
            reverseState->m_sourceTable.push_back(emptySourceList);

#ifdef _DEBUG
            vector<string> v;
            vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzpos;
            vector<CPKIFNameAndKeyWithScoreListPtr>::iterator zzzend = reverseState->m_table.end();
            for(zzzpos = reverseState->m_table.begin(); zzzpos != zzzend; ++zzzpos)
            {
                v.push_back((*zzzpos)->front()->GetNameAndKey()->GetSubjectName()->ToString());
                v.push_back((*zzzpos)->front()->GetNameAndKey()->GetIssuerName()->ToString());
            }
#endif

            return true;
        }
        else if(PBD_REVERSE == reverseState->m_direction &&
            *curCertAsNameAndKey->GetSubjectName() == *reverseState->m_targetCertAsNameAndKey->GetIssuerName())
        {
            //we're building backwards and have found one or more certs issued to the issuer of the target
            CPKIFNameAndKeyWithScoreListPtr newList(new CPKIFNameAndKeyWithScoreList);
            CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(reverseState->m_targetCertAsNameAndKey));
            newList->push_back(newNode);

            CPKIFCertificateSourceListPtr emptySourceList;
            reverseState->m_bTableIsComplete = true;

            reverseState->m_table.insert(reverseState->m_table.begin(),newList);
            reverseState->m_sourceTable.insert(reverseState->m_sourceTable.begin(), emptySourceList);
            return true;
        }
        else
        {
            //if reverse or not a trust anchor, grabbing from all sources with direction indicated by the state object
            CPKIFCertificatePtr curCert = dynamic_pointer_cast<CPKIFCertificate, IPKIFNameAndKey>(curCertAsNameAndKey);
            if(curCert == (CPKIFCertificate*)NULL)
            {
                CPKIFTrustRootPtr tr = dynamic_pointer_cast<CPKIFTrustRoot, IPKIFNameAndKey>(curCertAsNameAndKey);
                if(tr != (CPKIFTrustRoot*)NULL)
                    tr->GetCert(curCert);
            }

            if(curCert != (CPKIFCertificate*)NULL)
            {
                iCertSS->GetCertificateSources(curCert, certSourceList, reverseState->m_direction);
            }
            else if(PBD_FORWARD == reverseState->m_direction)
                iCert->GetCertificates(curCertAsNameAndKey->GetIssuerName(), certList, reverseState->m_sources);
            else
            {
                CPKIFException e(m_parent->thisComponent, COMMON_INVALID_INPUT, "Reverse direction building from non-certificate trust anchors is not supported");
                throw e;
            }
            
            if(certList.size() || certSourceList.size())
            {
                //at this point, we've retrieved all we can for the current cert (though we may not have 
                //retrieved them yet) and need to sort the list

                CPKIFNameAndKeyWithScoreListPtr newList(new CPKIFNameAndKeyWithScoreList);
                CPKIFCertificateNodeList::iterator cPos;
                CPKIFCertificateNodeList::iterator cEnd = certList.end();
                for(cPos = certList.begin(); cPos != cEnd; ++cPos)
                {
                    CPKIFCertificatePtr cPosAsCert = (*cPos)->GetCert();
                    IPKIFNameAndKeyPtr cPosAsNameAndKey = dynamic_pointer_cast<IPKIFNameAndKey, CPKIFCertificate>(cPosAsCert);
                    CPKIFNameAndKeyWithScorePtr newNode(new CPKIFNameAndKeyWithScore(cPosAsNameAndKey));
                    newList->push_back(newNode);
                }

                CPKIFCertificateSourceListPtr newSourceList(new CPKIFCertificateSourceList);
                copy(certSourceList.begin(), certSourceList.end(), back_inserter(*newSourceList));

                SortAndSaveLists(reverseState, newList, newSourceList);
            }

            //need to remove any certs that create loops with the current table
            RemoveLoopMakers(certList, reverseState);

            RemoveExtraneous(certList, reverseState);

            //if the table did not grow
            if(reverseState->m_table.size() == tableSize)
            {
                //this will either resolve a remote source that was just identified (if no
                //local sources were found) or punt the row
                PuntTopRow(reverseState);
            }
        }

        curCertAsNameAndKey = GetCurrentCert(reverseState);
    }while(curCertAsNameAndKey != (IPKIFNameAndKey*)NULL);

    if(curCertAsNameAndKey == (IPKIFNameAndKey*)NULL)
        return false;
    else
    {
        //need to mark nodes as ignored where the name chaining is broken
        CPKIFNamePtr issuerName;
        vector<CPKIFNameAndKeyWithScoreListPtr>::reverse_iterator pos;
        vector<CPKIFNameAndKeyWithScoreListPtr>::reverse_iterator end = reverseState->m_table.rend();
        for(pos = reverseState->m_table.rbegin(); pos != end; ++pos)
        {
            if(issuerName == (CPKIFName*)NULL)
                issuerName = (*pos)->front()->GetNameAndKey()->GetSubjectName();
            else
            {
                IgnoreNotIssuedBy(*pos, issuerName);
                issuerName = (*pos)->front()->GetNameAndKey()->GetSubjectName();
            }
        }

        return true;
    }

    return false;
}

bool CPKIFReversiblePathBuilderImpl::TriedBefore(CPKIFNameAndKeyWithScoreList& builtPathNK)
{
    std::vector<CPKIFNameAndKeyWithScoreList>::iterator pos;
    std::vector<CPKIFNameAndKeyWithScoreList>::iterator end = m_previouslyTriedPaths.end();
    for(pos = m_previouslyTriedPaths.begin(); pos != end; ++pos)
    {
        if((*pos).size() != builtPathNK.size())
            return false;

        for(size_t ii = 0; ii < (*pos).size(); ++ii)
        {
            if(!((*pos)[ii] == builtPathNK[ii]))
                return false;
        }
    }
    return !m_previouslyTriedPaths.empty();
}

bool CPKIFReversiblePathBuilderImpl::CheckAlternatives(CPKIFCertificatePath& path, CPKIFReversePathStatePtr& reverseState)
{
    //if the table is incomplete (i.e. there is only the root row or target row) return false
    if(1 >= reverseState->m_table.size())
        return false;

    CPKIFBuilderStatisticsPtr bs;
    path.GetBuilderStats(bs);

    do
    {
        if(reverseState->m_curRoot == NULL)
        {
            //we haven't been here before
            CPKIFNameAndKeyWithScorePtr rootNK = reverseState->m_table.back()->front();
            reverseState->m_curRoot = dynamic_pointer_cast<IPKIFTrustAnchor, IPKIFNameAndKey>(rootNK->GetNameAndKey());
        }
        else
        {
            //if we didn't move the ignore pointer on the root row
            vector<CPKIFNameAndKeyWithScoreListPtr>::iterator tablePos;
            vector<CPKIFNameAndKeyWithScoreListPtr>::iterator tableEnd = reverseState->m_table.end();
            for(tablePos = reverseState->m_table.begin(); tablePos != tableEnd; ++tablePos)
            {

#ifdef _DEBUG
                const char* frontNodeInCurRowName = (*tablePos)->front()->GetNameAndKey()->GetSubjectName()->ToString();
#endif
                if(!SetNextToIgnore(*tablePos))
                {
                    //if we do not need to advance the row then break out of this loop
                    break;
                }
                else
                {
                    //if we do need to advance the row the clear all ignored flags in the current row
                    ClearAllIgnore(*tablePos);
                }
            }
            if(tablePos == tableEnd)
            {
                bool liveMore = false;

                //advance the ignored pointer in the trust root list (if there's more than one root)
                if(reverseState->m_table.front()->size() > 1)
                {
                    bool setNext = false;
                    CPKIFNameAndKeyWithScoreList::iterator rootPos;
                    CPKIFNameAndKeyWithScoreList::iterator rootEnd = reverseState->m_table.front()->end();
                    for(rootPos = reverseState->m_table.front()->begin(); rootPos != rootEnd; ++rootPos)
                    {
                        IPKIFTrustAnchorPtr ta = dynamic_pointer_cast<IPKIFTrustAnchor, IPKIFNameAndKey>((*rootPos)->GetNameAndKey());
                        if(setNext)
                        {
                            reverseState->m_curRoot = ta;
                            liveMore = true;
                            break;
                        }
                        else
                        {
                            if(*reverseState->m_curRoot == *ta)
                                setNext = true;
                        }
                    }
                }
                
                if(!liveMore)
                {
                    return false;//no more alternatives in this table - return false
                }
            }
        }

        //this code iterates over the table and populates builtPath with the first non-ignored
        //node that isn't already in the path (same DN/same public key) that was issued by the previous
        //node in the list.
        CPKIFNameAndKeyWithScoreList builtPathNK;
        vector<CPKIFNameAndKeyWithScoreListPtr>::reverse_iterator pos;
        vector<CPKIFNameAndKeyWithScoreListPtr>::reverse_iterator end = reverseState->m_table.rend();
        CPKIFNameAndKeyWithScorePtr curEntry;
        bool hasCycle = false;
        PKIInfoSource pathMaxSource = LOCAL;

        IPKIFNameAndKeyPtr lastCert = dynamic_pointer_cast<IPKIFNameAndKey, IPKIFTrustAnchor>(reverseState->m_curRoot);

        CPKIFPathSettingsPtr settings; 
        path.GetPathSettings(settings);

        pos = reverseState->m_table.rbegin();
        for(++pos; pos != end; ++pos)
        { 
            curEntry = GetFirstNonIgnoredNodeNotAlreadyInPathIssuedBy(*pos, builtPathNK,lastCert,settings);
            if(curEntry != (CPKIFCertificateNodeEntry*)NULL     //check for NULL
                && !curEntry->GetNameAndKey()->SameDNSameKey(*lastCert))    //make sure TA DN and key are not repeated
            {
                builtPathNK.push_back(curEntry);

                IPKIFNameAndKeyPtr emptyNK;
                lastCert = emptyNK;
                lastCert = curEntry->GetNameAndKey();
            }
            else
            {
                hasCycle = true; //this path has a cycle - try another
                break;
            }
        }

        ++bs->m_nTotalPathsDiscovered;

        //if the effort to build through current table state produced a cycle 
        //give another pass through the do...while by moving the ignored pointer
        if(hasCycle || TriedBefore(builtPathNK))
            continue;

        m_previouslyTriedPaths.push_back(builtPathNK);

        CPKIFCertificateNodeList builtPath;
        CPKIFNameAndKeyWithScoreList::iterator nkPos;
        CPKIFNameAndKeyWithScoreList::iterator nkEnd = builtPathNK.end();

        for(nkPos = builtPathNK.begin();nkPos != nkEnd; ++nkPos)
        {
            CPKIFCertificatePtr tmpCert = dynamic_pointer_cast<CPKIFCertificate, IPKIFNameAndKey>((*nkPos)->GetNameAndKey());
            CPKIFCertificateNodeEntryPtr newNode(new CPKIFCertificateNodeEntry(tmpCert));
            builtPath.push_back(newNode);
        }


        //perform basic validation checks
        CPKIFPathValidationResults tmpResults;
        if(settings->GetUseValidatorFilterWhenBuilding() && !PathOK(builtPath, reverseState->m_curRoot, settings, tmpResults))
        {
            ++bs->m_nPathsRejectedDueToValidationErrors;
            bs->m_vFailureCodes.push_back(tmpResults.DiagnosticCode());
//          SearchForFailure(reverseState, builtPath);

            CPKIFCertificatePath tmpPath;
            CPKIFCertificatePtr tmpTarget;
            path.GetTarget(tmpTarget);
            tmpPath.SetTrustRoot(reverseState->m_curRoot);
            tmpPath.SetPath(builtPath);
            tmpPath.SetTarget(tmpTarget);

            CPKIFPathLogger::LogValidationResults(tmpResults, tmpPath, "Logging builder-rejected path"); //added 04/18/2003 CRW
            continue;
        }

        path.SetTrustRoot(reverseState->m_curRoot);
        path.SetPath(builtPath);

        CPKIFCertificateNodeList::iterator dbgpos;
        CPKIFCertificateNodeList::iterator dbgend = builtPath.end();
        if(LOCAL == pathMaxSource)
        {
            LOG_STRING_DEBUG("Printing path returned from BuildPath (LOCAL-certs only)...", m_parent->thisComponent, 0, NULL);
        }
        else
        {
            LOG_STRING_DEBUG("Printing path returned from BuildPath (LOCAL and REMOTE certs)...", m_parent->thisComponent, 0, NULL);
        }
        std::string logStr = "Root: ";
        logStr.append(((reverseState->m_curRoot))->GetSubjectName()->ToString());
        LOG_STRING_DEBUG(logStr.c_str(), m_parent->thisComponent, 0, NULL);

        for(dbgpos = builtPath.begin(); dbgpos != dbgend; ++dbgpos)
        {
            const char* curCertString = (*dbgpos)->GetCert()->Subject()->ToString();
            logStr = curCertString;
            logStr.append(" ");
            logStr.append((*dbgpos)->GetCert()->SerialNumber());
            LOG_STRING_DEBUG(logStr.c_str(), m_parent->thisComponent, 0, NULL);
        }
        ++bs->m_nReturnedPaths;
        return true;
    }while(1);

}


CPKIFReversiblePathBuilder::CPKIFReversiblePathBuilder(PathBuildingDirection pbd)
:m_impl(new CPKIFReversiblePathBuilderImpl)
{
    LOG_STRING_DEBUG("CPKIFReversiblePathBuilder::CPKIFReversiblePathBuilder", thisComponent, 0, this);
    m_impl->m_parent = this;
    m_impl->m_pbd = pbd;
}

CPKIFReversiblePathBuilder::~CPKIFReversiblePathBuilder(void)
{
    if(m_impl)
    {
        delete m_impl;
        m_impl = 0;
    }
}

void CPKIFReversiblePathBuilder::Initialize()
{
    LOG_STRING_DEBUG("CPKIFReversiblePathBuilder::Initialize()", thisComponent, 0, this);
}

bool CPKIFReversiblePathBuilder::BuildPath(
    CPKIFCertificatePath& path)
{
    LOG_STRING_DEBUG("CPKIFReversiblePathBuilder::BuildPath(CPKIFCertificatePath& path)", thisComponent, 0, this);

    //----------------------------------------------------------------------------------------------------
    // these may need to be parameters and this function simply invoked from the CPKIFPathBuild and CPKIFPathReverseBuild classes
    PathBuildingDirection pbd = m_impl->m_pbd;
    //PathBuildingDirection pbd = PBD_REVERSE;
    //----------------------------------------------------------------------------------------------------

    //throws if there are any problems
    m_impl->CheckInputs(path);

    //at this point, we know we have a target and we know we have an IPKIFTrustCache interface.  see if 
    //the target is a trust anchor.  if it is, the building operation is complete.
    CPKIFCertificatePtr targetCert;
    path.GetTarget(targetCert);
    if(m_impl->TargetIsTrustAnchor(targetCert))
    {
        //if we find a trust root that matches the target then we're done, no need to build state and so forth
        CPKIFTrustRootPtr tr(new CPKIFTrustRoot());
        tr->SetCert(targetCert);
        path.SetTrustRoot(tr);

        //then set the path to a list containing only the target
        CPKIFCertificateNodeList builtPath;
        CPKIFCertificateNodeEntryPtr curEntry(new CPKIFCertificateNodeEntry);
        curEntry->SetCert(targetCert);

        CPKIFCertStatusPtr newStatus(new CPKIFCertStatus);
        newStatus->SetIsTrustAnchor(true);
        curEntry->SetStatus(newStatus);

        builtPath.push_back(curEntry);
        path.SetPath(builtPath);

        std::ostringstream os;
        os << "Path building is not required.  The target certificate is a trust root - subject DN = " << targetCert->GetSubjectName()->ToString();
        LOG_STRING_INFO(os.str().c_str(), thisComponent, 0, this);

        return true;
    }

    //see if we have a state object
    CPKIFCertificatePathStatePtr state;
    path.GetState(state);

    //if there was state, see if we can cast it to a type that this builder uses
    CPKIFReversePathStatePtr reverseState = dynamic_pointer_cast<CPKIFReversePathState, CPKIFCertificatePathState>(state);
    if(state == (CPKIFCertificatePathState*)NULL || reverseState == (CPKIFReversePathState*)NULL)
    {
        //if not, set it aside and create a new state object
        m_impl->CreateState(path, pbd);
    }

    path.GetState(state);
    reverseState = dynamic_pointer_cast<CPKIFReversePathState, CPKIFCertificatePathState>(state);

    //at this point, we have a table in the state object.  we now need to add a row in the quest towards
    //building to the other end point.
    do
    {
        //if the table is complete and there's a viable alternative, return true and let the validator take over
        if(reverseState->m_bTableIsComplete && m_impl->CheckAlternatives(path, reverseState))
            return true;
    }while(m_impl->BuildOrGrowTable(reverseState));

    //no more paths - we could no longer grow the table and the current alternatives have been exhausted
    return false;   
}

PathBuildingDirection CPKIFReversiblePathBuilder::GetDirection() const
{
    return m_impl->m_pbd;
}