PKIFPathBuilder2.cpp

Go to the documentation of this file.

#include "PKIFPathBuilder2.h"
#include "PKIFBasicPathState2.h"
#include "PKIFPathSettings.h"
#include "IPKIFCertRepository.h"
#include "IPKIFCertRepositoryUpdate.h"
#include "IPKIFTrustCache.h"
#include "IPKIFCRLRepository.h"
#include "PKIFMediators.h"

#include "ToolkitUtils.h"
#include "BuilderUtils.h"
#include "BasicChecksUtils.h"
#include "GottaMatch.h"
#include "BuilderStatistics.h"

#include "PKIFPathException.h"
#include "PKIFErrors.h"
#include "PKIFCertificateNodeEntry.h"
#include "Name.h"
#include "Certificate.h"
#include "CertificateNodeListWithSourceInfo.h"
#include "PKIFDefaultScoring.h"
#include "PKIFTrustRoot.h"
#include "NodeInNodeList.h"
#include "PKIFCertStatus.h"
#include "PKIFCertificatePath.h"
#include "PKIFPathLogger.h"
#include "PathResults.h"
#include "AuthorityKeyIdentifier.h"
#include <sstream>

#include <boost/shared_ptr.hpp>
#include "boost/numeric/conversion/cast.hpp"

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

#include <iterator>

using namespace std;
using namespace boost;


extern bool KeyIDsMatch(CPKIFAuthorityKeyIdentifierPtr& akid, const IPKIFTrustAnchorPtr& curCert);

#ifdef _DEBUG_PATH_DUMP
#include <fstream>
ofstream g_pathLogFile;
#endif

class KeyIDCompare
{
public:
    bool operator()(const IPKIFTrustAnchorPtr& lhsTA, const IPKIFTrustAnchorPtr& rhsTA)
    {
        int lhsScore = 0, rhsScore = 0;

        CPKIFAuthorityKeyIdentifierPtr akid = m_currentCert->GetExtension<CPKIFAuthorityKeyIdentifier>();

        if(lhsTA)
        {
            if(KeyIDsMatch(akid, lhsTA))
            {
                lhsScore+=5;
            }
        }
        if(rhsTA)
        {
            if(KeyIDsMatch(akid, rhsTA))
            {
                rhsScore+=5;
            }
        }

        return lhsScore > rhsScore;
    }
    void SetCurrent(
        const CPKIFCertificatePtr& current) {m_currentCert = current;}
private:
    CPKIFCertificatePtr m_currentCert;
};

struct CPKIFPathBuilder2Impl 
{
    CPKIFPathBuilder2 *m_parent;

    //function that builds a table or grows a table by extending rows with additional sources
    bool BuildOrGrowTable(CPKIFBasicPathState2* basicState, CPKIFPathSettingsPtr& settings, CPKIFCertificatePtr& curCert, CPKIFCertificateNodeList& prevPath);

    //function that actually handles growing rows with additional sources
    bool GrowTable(CPKIFBasicPathState2* basicState, IPKIFCertRepository* iCert, 
        IPKIFCertRepositoryUpdate* iCertUpdate, IPKIFTrustCache* iTrust, CPKIFPathSettingsPtr& settings);

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

    //function that removes the current root row from the table
    //added roots param and associated processing 12/4/2003
    void PuntCurrentRoot(CPKIFBasicPathState2* basicState, IPKIFTrustAnchorList& roots);

    //function that removes the current row nearest the root
    bool PuntTopRow(CPKIFBasicPathState2* basicState, CPKIFNamePtr& prevName, 
        CPKIFCertificatePtr& curCert, IPKIFCertRepository* iCert, IPKIFCertRepositoryUpdate* iCertUpdate,
        IPKIFTrustCache* iTrust, CPKIFPathSettingsPtr& settings);

    //function that removes certs from a list that would create a loop in the current path
    void RemoveLoopMakers(CPKIFCertificateNodeList& certList, CPKIFBasicPathState2* basicState, CPKIFCertificateNodeListWithSourceInfoPtr& currPos, bool growingRow = false);

    void SearchForFailure(CPKIFBasicPathState2* basicState, CPKIFCertificateNodeList& prevPath, CPKIFPathSettingsPtr& settings);
    bool PuntFailure(CPKIFBasicPathState2* basicState, CPKIFCertificateNodeEntryPtr& ppPos);

    bool GrowRow(CPKIFCertificateNodeListWithSourceInfoPtr& pos, IPKIFCertRepository* iCert, IPKIFCertRepositoryUpdate* iCertUpdate, CPKIFBasicPathState2* basicState, 
        CPKIFCertificatePtr& curCert, IPKIFTrustCache* iTrust, CPKIFPathSettingsPtr& settings, CPKIFCertificateNodeListWithSourceInfoPtr& posPlusOne);
};

CPKIFPathBuilder2::CPKIFPathBuilder2(void)
:m_impl(new CPKIFPathBuilder2Impl)
{
    LOG_STRING_DEBUG("CPKIFPathBuilder2::CPKIFPathBuilder2", thisComponent, 0, this);
    m_impl->m_parent = this;
}
CPKIFPathBuilder2::~CPKIFPathBuilder2(void)
{
    LOG_STRING_DEBUG("CPKIFPathBuilder2::~CPKIFPathBuilder2", thisComponent, 0, this);
    
    delete m_impl;
    m_impl = 0;
}
void CPKIFPathBuilder2::Initialize() 
{
    LOG_STRING_DEBUG("CPKIFPathBuilder2::Initialize()", thisComponent, 0, this);
}

//----------------------------------------------------------------------------------------------------
//
//  Private interface functions
//
//----------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------
//  GrowTable (called from BuildOrGrowTable, GrowTable and PuntTopRow)
//      This function tries to expand the existing table by consulting REMOTE sources
//      for rows that were built entirely from LOCAL sources.  After calling this function
//      all rows in the table will have been expanded if possible.  All rows are done at once to 
//      simplify the code in CheckAlternatives that screens for previously returned paths.
//----------------------------------------------------------------------------------------------------
bool CPKIFPathBuilder2Impl::GrowRow(
    CPKIFCertificateNodeListWithSourceInfoPtr& pos, 
    IPKIFCertRepository* iCert, 
    IPKIFCertRepositoryUpdate* iCertUpdate,
    CPKIFBasicPathState2* basicState,
    CPKIFCertificatePtr& curCert, 
    IPKIFTrustCache* iTrust, 
    CPKIFPathSettingsPtr& settings,
    CPKIFCertificateNodeListWithSourceInfoPtr& posPlusOne)
{
    if(LOCAL == pos->m_maxSource)
    {
        //it may not actually be local because items from the in memory cache
        //may actually have been remote during this session.  if this is the case then
        //we want to avoid another (unnecessary) REMOTE attempt
        CPKIFCertificateNodeListWithSourceInfo::iterator nodeListPos;
        CPKIFCertificateNodeListWithSourceInfo::iterator nodeListEnd = pos->end();
        for(nodeListPos = pos->begin(); nodeListPos != nodeListEnd; ++nodeListPos)
        {
            if(LOCAL != (*nodeListPos)->GetSource())
                return false;//bail out now rather than try another REMOTE attempt
        }
    }

    if(NULL == basicState->m_reserved)
        return false;

    CPKIFCertificatePtr frontCert = pos->front()->GetCert();
    CPKIFNamePtr curCertSubject = frontCert->Subject();
    CPKIFCertificateNodeList certList;

    //added 7/22/2004 to check AIA/IAN
    //changed iterator declaration 11/23/2004
    //CPKIFCertificateNodeListWithSourceInfo::iterator tPos = posPlusOne->begin();
    //CPKIFCertificateNodeListWithSourceInfo::iterator tEnd = posPlusOne->end();
    //for(;tPos != tEnd; ++tPos)
    //{
    //  CPKIFCertificatePtr tCert = (*tPos)->GetCert();
    //  GetCertsFromIssuerAltName(*tCert, certList);
    //}

    if(posPlusOne)
    {
        CPKIFCertificateNodeListWithSourceInfo::iterator tPos = posPlusOne->begin();
        CPKIFCertificateNodeListWithSourceInfo::iterator tEnd = posPlusOne->end();
        for(;tPos != tEnd; ++tPos)
        {
            CPKIFCertificatePtr tCert = (*tPos)->GetCert();
            iCert->GetCertificates(tCert, certList, REMOTE);
        }
    }

    //the commenting of the following two lines was reversed to avoid using the interface that does not use the syn store when building
    //iCert->GetCertificates(curCertSubject, certList, REMOTE);
    iCert->GetCertificates(frontCert, certList, REMOTE);

    pos->m_maxSource = REMOTE; //added 8/27/2004
    basicState->m_maxSource = ALL;
    size_t certListSize = certList.size();
    if(0 != certListSize)
    {
        //remove any certs that would create a loop with certs already in the path
        RemoveLoopMakers(certList, basicState, pos, true);
        certListSize = certList.size();
    }
    
    if(0 == certListSize)
        return false;
    else
    {
        bool retval = false;

        //code in this block is very similar to code in BuildAndGrowTable - if modify here investigate there
        CPKIFCertificateNodeList::iterator certListPos;
        CPKIFCertificateNodeList::iterator certListEnd = certList.end();
        for(certListPos = certList.begin(); certListPos != certListEnd; ++certListPos)
        {
            //make sure we ignore certs for other folks that may have been in the directory
            if(*curCertSubject == *(*certListPos)->GetCert()->Subject())
            {
                GottaMatch<CPKIFCertificateNodeEntryPtr> gm;
                gm.SetRHS(*certListPos);
                if(pos->end() == find_if(pos->begin(), pos->end(), gm))
                {
                    //if we found certs - add them to the LOCAL cache
                    if(iCertUpdate && LOCAL != (*certListPos)->GetSource())
                    {
                        try
                        {
                            iCertUpdate->AddCertificate(CA, *certListPos);
                        }
                        catch(CPKIFException&)
                        {
                            //delete e;//don't fail because we have no in-memory cache or whatever
                        }
                    }

                    basicState->m_maxSource = ALL;
                    pos->push_back(*certListPos);
                    pos->m_maxSource = ALL;
                    retval = true;
                }
            }//end if curCert subject matches certListPos subject
        }//end iteration over certList

        if(retval)
        {
            //eliminate template and always use the default scoring class
            CPKIFDefaultScoring s;

            //Scoring s;    //create an object of the type defined by the template parameter

            //reviewed 4/24 - the path depth is governed by an integer value so size_t should never exceed that value (or even come close)
            int size = 0;
            try 
            {
                size = numeric_cast<int>(basicState->m_table.size());
            }
            catch(bad_numeric_cast &) 
            {
                throw CPKIFException(TOOLKIT_PATH, COMMON_INVALID_INPUT, "Bable size is an impossibly long number.");
            }
            s.ScoreAndSortNodes(pos, curCert, settings, iTrust, size - 1,iCert);//-1 to not count target cert
            retval = pos->size() != 0;
        }

        return retval;
    }//end else 0 != certListSize
}

//----------------------------------------------------------------------------------------------------
//  GrowTable (called from BuildOrGrowTable)
//      This function tries to expand the existing table by consulting REMOTE sources
//      for rows that were built entirely from LOCAL sources.  After calling this function
//      all rows in the table will have been expanded if possible.  All rows are done at once to 
//      simplify the code in CheckAlternatives that screens for previously returned paths.
//----------------------------------------------------------------------------------------------------
bool CPKIFPathBuilder2Impl::GrowTable(
    CPKIFBasicPathState2* basicState, 
    IPKIFCertRepository* iCert,
    IPKIFCertRepositoryUpdate* iCertUpdate, 
    IPKIFTrustCache* iTrust, 
    CPKIFPathSettingsPtr& settings)
{
    bool retVal = false;

    CPKIFCertificatePtr curCert;
    if(!basicState->m_table.empty())
    {
        //should always get here
        curCert = basicState->m_table.front()->front()->GetCert(); //should be only
    }
/*  if(NULL != basicState->m_curRoot)
    {
        //XXX***TA TEMP WORKAROUND
        CPKIFTrustRoot* ta = dynamic_cast<CPKIFTrustRoot*>(&(*(*basicState->m_curRoot)));
        if(ta != NULL)
            ta->GetCert(curCert);
    }
    else if(!basicState->m_rootList.empty())
    {
        //XXX***TA TEMP WORKAROUND
        CPKIFTrustRoot* ta = dynamic_cast<CPKIFTrustRoot*>(&(*(basicState->m_rootList.front())));
        if(ta != NULL)
            ta->GetCert(curCert);
    }
    else
    {
        //huh?
    }
*/

    //probably isn't necessary to use reverse iterators (except when assembling a path for return)
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator pos = basicState->m_table.rbegin();
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator end = basicState->m_table.rend();
    for(; pos != end; ++pos)
    {
        //only pursue rows that haven't previously been pursued beyond LOCAL (and that aren't empty)
        //never try to grow the target row
        if(LOCAL == (*pos)->m_maxSource && !(*pos)->empty() && (pos + 1) != end)
        {
            if(GrowRow(*pos, iCert, iCertUpdate, basicState, curCert, iTrust, settings, *(pos + 1)))
            {
                retVal = true;
                if(basicState->m_table.rbegin() == pos)
                {
                    basicState->m_curRoot = NULL;
                }
            }
        }//end LOCAL == maxSource

        if(0 == (*pos)->size())
            return false;
        else
            curCert = (*pos)->front()->GetCert();
    }//end table iteration

    return retVal;
}

//----------------------------------------------------------------------------------------------------
//  PuntCurrentRoot (called from BuildOrGrowTable)
//      This function simply empties the root list forcing a subsequent BuildOrGrowTable activity
//      to build to a new root.
//----------------------------------------------------------------------------------------------------
void CPKIFPathBuilder2Impl::PuntCurrentRoot(
    CPKIFBasicPathState2* basicState, 
    IPKIFTrustAnchorList& oldRoots)
{
    //copy the current roots into the oldRoots outbound parameter
    copy(basicState->m_rootList.begin(), basicState->m_rootList.end(), back_inserter(oldRoots));

    //attempts to build to the current root have proven fruitless - empty the root list
    basicState->m_rootList.clear();

    //clean up the state
    basicState->ClearState();
}

//----------------------------------------------------------------------------------------------------
//  RemoveLoopMakers (called from PuntTopRow, GrowTable and BuildOrGrowTable)
//      This function builds a partial path by taking the front node from each row
//      and removes certs from the certList parameter object that would create a loop
//      with any of those certs.  Comparison uses same DN/same public key logic.
//----------------------------------------------------------------------------------------------------
void CPKIFPathBuilder2Impl::RemoveLoopMakers(
    CPKIFCertificateNodeList& certList, 
    CPKIFBasicPathState2* basicState, 
    CPKIFCertificateNodeListWithSourceInfoPtr& currPos, 
    bool growingRow)
{
    //if the table is empty then there are no "loop makers" - return immediately
    if(basicState->m_table.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)
    CPKIFCertificateNodeList builtPath;
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator pos = basicState->m_table.rbegin();
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator end = basicState->m_table.rend();
    if(growingRow && pos != end)
        ++pos;//don't remove items that conflict with the current node closest to root

    CPKIFCertificatePtr currPosCert = currPos->front()->GetCert();
    while(pos != end && !(*pos)->empty() && !(*(*pos)->front()->GetCert() == *currPosCert))
    {
        ++pos;
    }

    //if(pos != end)
    //  ++pos;

    for(; pos != end; ++pos)
    {
        if(!(*pos)->empty())
            builtPath.push_back((*pos)->front());
    }

#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

    //next remove any duplicates from the current list
    //for(CPKIFCertificateNodeList::size_type ii = 0; ii < certList.size(); ++ii)
    //{
    //  for(CPKIFCertificateNodeList::size_type jj = ii+1; jj < certList.size(); ++jj)
    //  {
    //      if(*certList[ii] == *certList[jj])
    //      {
    //          certList.erase(certList.begin() + jj);
    //          jj = ii+1;
    //      }
    //  }
    //}
}

//----------------------------------------------------------------------------------------------------
//  PuntTopRow
//----------------------------------------------------------------------------------------------------
bool CPKIFPathBuilder2Impl::PuntTopRow(
    CPKIFBasicPathState2* basicState,
    CPKIFNamePtr& prevName, 
    CPKIFCertificatePtr& curCert, 
    IPKIFCertRepository* iCert,
    IPKIFCertRepositoryUpdate* iCertUpdate, 
    IPKIFTrustCache* iTrust, 
    CPKIFPathSettingsPtr& settings)
{
    //basicState holds the table of certs, prevName holds the name of the issuer we are giving up on
    //and curCert will be set to the curCert used for building upon exiting this function.
    //thus basicState - in/out; prevName - in; curCert - out

    //set curCert to NULL - we'll set it to an actual cert below if possible
    CPKIFCertificatePtr nullCert;
    curCert = nullCert; 

    //the top of the table is the end of the vector - iterate in reverse
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator pos = basicState->m_table.rbegin();
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator end = basicState->m_table.rend();
    do
    {
        //this loop should never punt the last row in the table
        for(; pos != end && (pos+1) != end; ++pos)
        {
            //before punting this row - see if it can be grown using remote sources
            if(LOCAL == (*pos)->m_maxSource && !(*pos)->empty() && (pos + 1) != end)
            {
                LOG_STRING_INFO("Failed to find necessary certificates using LOCAL sources.  Checking REMOTE sources.", m_parent->thisComponent, 0, this);
                if(GrowRow(*pos, iCert, iCertUpdate, basicState, curCert, iTrust, settings, *(pos + 1)))
                    break;
            }

            //get the name of the subject at the front of the current row
            CPKIFNamePtr tmpName = (*pos)->front()->GetCert()->Subject();

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

            //remove all certs in the current row that were issued by prevName
            RemoveAllIssuedBy(*pos, prevName);

#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
            prevName = tmpName;

            //if the current row is not empty after the above remove call then there's still hope
            if(!(*pos)->empty())
                break;
        }

        //if pos != end then set the curCert to the front cert on the pos row (this will cause loop termination
        if(pos != end && (pos+1) != end)
            curCert = (*pos)->front()->GetCert(); 
        else
            break;//if pos == end break out by force
    }while(curCert == (CPKIFCertificate*)NULL);

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

//#ifdef _DEBUG_PATH
    //cout << endl << "Dumping table from PuntTopRow" << endl;
    //DumpTable(basicState->m_table, "PuntTopRow");
//#endif

    //if we exited the above loop with curCert == NULL then building is done (and failed)
    if(curCert == (IPKIFNameAndKey*)NULL || basicState->m_table.size() == 0)
        return false;
    else 
    {
        basicState->m_bInitCompleteLocal = false; //this isn't true for roots after first root 
        return true;//otherwise - we can continue trying to build
    }
}

//----------------------------------------------------------------------------------------------------
//  PuntFailure
//----------------------------------------------------------------------------------------------------
bool CPKIFPathBuilder2Impl::PuntFailure(
    CPKIFBasicPathState2* basicState, 
    CPKIFCertificateNodeEntryPtr& ppPos)
{
    //This function will remove the node in ppPos from the table of nodes from which we build paths.
    //If removal of the node causes the list to become empty then the row and all rows from it to the root are removed
    CPKIFNamePtr nodeName = ppPos->GetCert()->Subject();
    CPKIFNamePtr nextNodeName;
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator pos = basicState->m_table.rbegin();
    vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator end = basicState->m_table.rend();
    for(; pos != end; ++pos)
    {
        CPKIFNamePtr tmpName = (*pos)->front()->GetCert()->Subject();

#ifdef _DEBUG
        const char* curNodeString = nodeName->ToString();
        const char* curCertSubjectString = tmpName->ToString();
#endif

        if(*tmpName == *nodeName)
        {
            size_t size = (*pos)->size();
            GottaMatch<CPKIFCertificateNodeEntryPtr > gm;
            gm.SetRHS(ppPos);
            //changed iterator declaration 11/23/2004
            CPKIFCertificateNodeListWithSourceInfo::iterator newEnd = remove_if((*pos)->begin(), (*pos)->end(), gm);
            (*pos)->erase(newEnd, (*pos)->end());

            size = (*pos)->size();
            if(0 == size)
            {
                //we've emptied a row in our table so we should remove the top
                basicState->m_rootList.clear();

                //remove the cert in the previous row that caused the violater to be retrieved
                int indexer = 0;
                
                do
                {
                    ++indexer;

                    //if the next row is the end then break
                    if((pos+indexer) == end)
                        break;

                    //get the name of the front cert in the next row
                    nextNodeName = (*(pos+indexer))->front()->GetCert()->Subject();

                    //this may cause the last row in the table to be removed.  this is OK since it means the target was the cause of the failure.
                    //otherwise remove all nodes in the next row issued by nodeName 
                    RemoveAllIssuedBy(*(pos+indexer), nodeName);

                    //set up nodeName for next iteration
                    nodeName = nextNodeName;
                }while(0 == (*(pos+indexer))->size()); //keep going until end of table as long as rows continue to be made empty

                vector<CPKIFCertificateNodeListWithSourceInfoPtr>::iterator newEnd = find_if(basicState->m_table.begin(), basicState->m_table.end(), IsEmpty);
                basicState->m_table.erase(newEnd, basicState->m_table.end());
            }
            break;
        }
    }

    if(0 == basicState->m_table.size())
        return false;
    else 
    {
        return true;
    }
}

//----------------------------------------------------------------------------------------------------
//  SearchForFailure
//----------------------------------------------------------------------------------------------------
void CPKIFPathBuilder2Impl::SearchForFailure(
    CPKIFBasicPathState2* basicState, 
    CPKIFCertificateNodeList& prevPath,
    CPKIFPathSettingsPtr& settings)
{
    CPKIFGeneralSubtreeListPtr perm, excl;
    settings->GetInitialPermSubtrees(perm);
    settings->GetInitialExclSubtrees(excl);
    bool permHasBeenSet = false;
    if(perm)
        permHasBeenSet = true;

    CPKIFCertificateNodeList::iterator ppPos;   
    CPKIFCertificateNodeList::iterator ppEnd = prevPath.end();
    bool removeTheOffendingCert = false;
    for(ppPos = prevPath.begin(); ppPos != ppEnd; ++ppPos)
    {
        CPKIFCertStatusPtr status = (*ppPos)->GetStatus();

        if(status)
        {
            //these are events that allow us to remove a cert from further consideration
            //with the current set of certs above it
            if(PATH_NAME_CONSTRAINTS_VIOLATION == status->GetDiagnosticCode())
            {
                CPKIFCertificatePtr cert = (*ppPos)->GetCert();
                if(!CheckNameConstraints(cert, perm, excl, permHasBeenSet))
                    removeTheOffendingCert = true;
                break;
            }
            else if(REVOKED == status->GetRevocationStatus())
            {
                removeTheOffendingCert = true;
                break;
            }
            else if(ppPos == ppEnd -1 && 
                (PATH_VALIDITY_PERIOD_VIOLATION_NOT_YET_VALID == status->GetDiagnosticCode()
                || PATH_VALIDITY_PERIOD_VIOLATION_EXPIRED == status->GetDiagnosticCode()))
            {
                removeTheOffendingCert = true;
                break;
            }
        }
    }

    if(ppPos != ppEnd)
    {
        if(removeTheOffendingCert)
        {
            //remove the cert that caused the failure
            PuntFailure(basicState, *ppPos);
        }
        else
            (*ppPos)->SetIgnore();
    }
}

//----------------------------------------------------------------------------------------------------
//  BuildOrGrowTable
//----------------------------------------------------------------------------------------------------
bool CPKIFPathBuilder2Impl::BuildOrGrowTable(
    CPKIFBasicPathState2* basicState, 
    CPKIFPathSettingsPtr& settings, 
    CPKIFCertificatePtr& curCert,
    CPKIFCertificateNodeList& prevPath)
{
    //----------------------------------------------------------------------------------------------------
    //  COLLECT INTERFACES
    //----------------------------------------------------------------------------------------------------
    //query for the various interfaces we will need:
    //  need: IPKIFCertRepository, IPKIFTrustCache
    //  use (if present): IPKIFCertRepositoryUpdate, IPKIFCRLRepository
    //  future:   ICACPathCache
    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 update interface can be absent (if it's present we'll use it)
    IPKIFCertRepositoryUpdate* iCertUpdate = m_parent->GetMediatorFromParent<IPKIFCertRepositoryUpdate>();

    //likewise for the CRL interface
    IPKIFCRLRepository* iCRL = m_parent->GetMediatorFromParent<IPKIFCRLRepository>();

    //this interface doesn't exist - but we'll query for it anyway to recall the days when it's existance was anticipated (or not)
    //ICACPathCache* iPath = GetMediatorFromParent<ICACPathCache>();

    bool skipRootCheck = false; //this flag is used to indicate that we just punted a root and should try alternatives from top row of table
    //eliminate template and always use the default scoring class
    CPKIFDefaultScoring s;
    //Scoring s;    //create an object of the type defined by the template parameter

    IPKIFTrustAnchorList oldRoots;

    //see if the root list is empty - if not try to grow the table or get rid of the root (and any other garbage)
    if(!basicState->m_rootList.empty())
    {
        //try to add to the table using additional sources
        if(GrowTable(basicState, iCert, iCertUpdate, iTrust, settings))
            return true;

        //if we failed to add any new entries then punt the current root
        PuntCurrentRoot(basicState, oldRoots);
        skipRootCheck = true; //there may be alternatives to using top row to trust root connection

        //the top of the table is the end of the vector.  take the front cert from the top row
        //by taking the front cert from the last entry in the vector
        if(!basicState->m_table.empty() && !basicState->m_table.back()->empty())
            curCert = basicState->m_table.back()->front()->GetCert();
        else
        {
            return false;//we're done
        }
    }
    else if(curCert == (CPKIFCertificate*)NULL)
    {
        return false;
    }

    //we're rootless - create a new empty root list to realize that fact
    IPKIFTrustAnchorList trustRootList;
    CPKIFNamePtr curCertIssuer, curCertSubject;
    
    //when we find a path we'll set this guy to true - for now (s)he's false (pause to ponder the gender of variables)
    bool foundPath = false;

    PKIInfoSource oldSource = basicState->m_maxSource;

    size_t tableSize = 0;
    do
    {
        
        tableSize = basicState->m_table.size(); //harvest table size for use by scoring function
        curCertIssuer = curCert->GetIssuerName();       //save the issuer of the current cert

#ifdef _DEBUG
        curCertSubject = curCert->GetSubjectName(); 
        const char* curCertIssuerString = curCertIssuer->ToString();
        const char* curCertSubjectString = curCertSubject->ToString();
#endif

        //only look for trust roots when we didn't just punt the root row (otherwise we'll sit and spin)
        if(!skipRootCheck && iTrust->GetTrustRoots(curCertIssuer, trustRootList))
        {
            KeyIDCompare keyIDComp;
            keyIDComp.SetCurrent(curCert);  
            sort(trustRootList.begin(), trustRootList.end(), keyIDComp);

            //we've found a trust root so we can return a path
            basicState->SetTrustRoot(trustRootList);

            foundPath = true;
            break;
        }
        else
        {
            skipRootCheck = false;  //reset so we'll look for roots next pass

            CPKIFCertificateNodeList certList;
            //CPKIFCertificateList certList;

            //the cur cert is not issued by a trust root (more or less) - look for certs elsewhere
            //iCert->GetCertificates(curCertIssuer, certList, basicState->m_maxSource);
            iCert->GetCertificates(curCert, certList, basicState->m_maxSource);
            size_t certListSize = certList.size();
            do
            {
                if((0 == certListSize || LOCAL < basicState->m_maxSource) && NULL != basicState->m_reserved /*&& LOCAL == basicState->m_maxSource*/)
                {
                    LOG_STRING_INFO("Failed to find necessary certificates using LOCAL sources.  Checking REMOTE sources.", m_parent->thisComponent, 0, this);

                    //moved down here from above so it is only invoked when REMOTE sources are considered
                    //GetCertsFromIssuerAltName(*curCert, certList, REMOTE); //added 04/17/2003 CRW

                    //if local failed to produce results - try remote
                    //iCert->GetCertificates(curCertIssuer, certList, REMOTE);
                    iCert->GetCertificates(curCert, certList, REMOTE);
                    certListSize = certList.size();
                    //if(0 != certListSize)
                        basicState->m_maxSource = ALL;//only bump this if we found some certs (if we didn't we may still be able to build through the cache)
                }

                if(0 != certListSize)
                {
                    //remove any certs that would create a loop with certs already in the path
                    RemoveLoopMakers(certList, basicState, *basicState->m_table.rbegin());

                    //added 12/4
                    IPKIFTrustAnchorList::iterator orPos;
                    IPKIFTrustAnchorList::iterator orEnd = oldRoots.end();
                    for(orPos = oldRoots.begin(); orPos != orEnd; ++orPos)
                    {
                        //if we just punted a specific root - don't use it again
                        //not accounting for non-cert TAs in this case
                        CPKIFCertificatePtr taCert = (*orPos)->GetCertificate();
                        if(taCert)
                        {
                            CPKIFCertificateNodeEntryPtr newNode(new CPKIFCertificateNodeEntry);
                            newNode->SetCert(taCert);

                            GottaMatch<CPKIFCertificateNodeEntryPtr> orGM;
                            orGM.SetRHS(newNode);

                            CPKIFCertificateNodeList::iterator newEnd = remove_if(certList.begin(), certList.end(), orGM);
                            certList.erase(newEnd, certList.end());
                        }
                    }

                    certListSize = certList.size();
                }
            }
            while(0 == certListSize && LOCAL == basicState->m_maxSource && NULL != basicState->m_reserved);//added do/while 7/24/2004

            if(0 == certListSize)
            {
                //if we found no certs (or all of the found certs created loops) then punt the top row
                PuntTopRow(basicState, curCertIssuer, curCert, iCert, iCertUpdate, iTrust, settings);
                //Added to fix a problem when building in a bridge environment using only local store Armen 7/20/06
                if(basicState->m_maxSource == REMOTE)
                    basicState->m_maxSource = ALL;
            }
            else
            {
                //code in this block is very similar to code in GrowRow - if modify here investigate there

                //first convert the list of certs to a list of certnodes (i.e.
                //wrap the certs in a container that has information to guide
                //building and validation given the current settings)
                CPKIFCertificateNodeListWithSourceInfoPtr tmpNodeList(new CPKIFCertificateNodeListWithSourceInfo);
                tmpNodeList->m_maxSource = basicState->m_maxSource;
                CPKIFCertificateNodeList::iterator pos;
                CPKIFCertificateNodeList::iterator end = certList.end();
                for(pos = certList.begin(); pos != end; ++pos)
                {
                    //make sure we ignore certs for other folks that may have been in the directory
                    if(*curCertIssuer == *(*pos)->GetCert()->Subject())
                    {
                        GottaMatch<CPKIFCertificateNodeEntryPtr> gm;
                        gm.SetRHS(*pos);
                        if(tmpNodeList->end() == find_if(tmpNodeList->begin(), tmpNodeList->end(), gm))
                        {
                            //if we found certs - add them to the cache
                            if(iCertUpdate && LOCAL != (*pos)->GetSource())
                            {
                                try
                                {
                                    iCertUpdate->AddCertificate(CA, *pos);
                                }
                                catch(CPKIFException& )
                                {
                                    //delete e;//don't fail because we have no in-memory cache or whatever
                                }
                            }

                            tmpNodeList->push_back(*pos);
                        }
                    }
                }

                //sort the certs in the node and set curCert to the best
                //reviewed 4/24 - the path depth is governed by an integer value so size_t should never exceed that value (or even come close)
                
                int size = 0;
                try 
                {
                    size = numeric_cast<int>(basicState->m_table.size());
                }
                catch(bad_numeric_cast &) 
                {
                    throw CPKIFException(TOOLKIT_PATH, COMMON_INVALID_INPUT, "Table size is an impossibly long number.");
                }
                s.ScoreAndSortNodes(tmpNodeList, curCert, settings, iTrust, size - 1, iCert);//-1 to not count target cert

                //added table size check (Armen) 7/20/2004
                size_t stDepth = settings->GetDepth();
                if(0 != tmpNodeList->size() && tableSize < stDepth)
                {
                    basicState->m_table.push_back(tmpNodeList);
                    curCert = tmpNodeList->front()->GetCert(); 
                }
                else
                {
                    PuntTopRow(basicState, curCertIssuer, curCert, iCert, iCertUpdate, iTrust, settings);
                    //Added to fix a problem when building in a bridge environment using only local store Armen 7/20/06
                    if(basicState->m_maxSource == REMOTE)
                        basicState->m_maxSource = ALL;
                }
            }

            if(curCert == (CPKIFCertificate*)NULL)
                break;
        }
    }while(1);

    if(curCert == (CPKIFCertificate*)NULL)
        return false;
    else
    {
        if(oldSource != basicState->m_maxSource)
        {
            //if we changed from LOCAL to REMOTE in the above loop make sure all rows are
            //using the same max source so we can easily screen for previously returned paths
            //following a table expansion
            GrowTable(basicState, iCert, iCertUpdate, iTrust, settings);
        }
        if(0 == basicState->m_nGrowCount && LOCAL == basicState->m_maxSource)
            basicState->m_bInitCompleteLocal = true;

        ++basicState->m_nGrowCount;

        vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator pos;
        vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator end = basicState->m_table.rend();
        CPKIFNamePtr issuerName = basicState->m_rootList.front()->GetSubjectName();
        for(pos = basicState->m_table.rbegin(); pos != end; ++pos)
        {
            IgnoreNotIssuedBy(*pos, issuerName);
            issuerName = (*pos)->front()->GetCert()->Subject();
        }

        return true;
    }
}

//----------------------------------------------------------------------------------------------------
//  CheckAlternatives
//----------------------------------------------------------------------------------------------------
bool CPKIFPathBuilder2Impl::CheckAlternatives(
    CPKIFCertificatePath& path,
    CPKIFBasicPathState2* basicState)
{
    //if the table is incomplete (i.e. there is no root) return false
    //check for empty table added to account for cases where target was popped by PuntFailure
    if(basicState->m_rootList.empty() || 0 == basicState->m_table.size())
        return false;
    CPKIFBuilderStatisticsPtr bs;
    path.GetBuilderStats(bs);

    do
    {
        if(basicState->m_curRoot == NULL)
        {
            //we haven't been here before
            basicState->m_curRoot = &basicState->m_rootList.front();
        }
        else
        {
            //if we didn't move the ignore pointer on the root row
            vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator tablePos;
            vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator tableEnd = basicState->m_table.rend();
            for(tablePos = basicState->m_table.rbegin(); tablePos != tableEnd; ++tablePos)
            {
                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(basicState->m_rootList.size() > 1)
                {
                    bool setNext = false;
                    IPKIFTrustAnchorList::iterator rootPos;
                    IPKIFTrustAnchorList::iterator rootEnd = basicState->m_rootList.end();
                    for(rootPos = basicState->m_rootList.begin(); rootPos != rootEnd; ++rootPos)
                    {
                        if(setNext)
                        {
                            basicState->m_curRoot = &(*rootPos);
                            liveMore = true;
                            break;
                        }
                        else
                        {
                            if(basicState->m_curRoot == &(*rootPos))
                                setNext = true;
                        }
                    }
                }
                
                if(!liveMore)
                    return false;//no more alternatives in this table - return false
            }
        }

//#ifdef _DEBUG_PATH
        //DumpTable(basicState->m_table, "CheckAlternatives");
//#endif
        //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.
        CPKIFCertificateNodeList builtPath;
        vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator pos;
        vector<CPKIFCertificateNodeListWithSourceInfoPtr>::reverse_iterator end = basicState->m_table.rend();
        CPKIFCertificateNodeEntryPtr curEntry;
        bool hasCycle = false;
        PKIInfoSource pathMaxSource = LOCAL;
        CPKIFNamePtr issuerName = (*basicState->m_curRoot)->GetSubjectName();

        IPKIFNameAndKey* lastCert = dynamic_cast<IPKIFNameAndKey*>(&(*(*basicState->m_curRoot)));
        IPKIFNameAndKey* taCert = lastCert;

        CPKIFPathSettingsPtr settings; 
        path.GetPathSettings(settings);

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

                lastCert = NULL;
                lastCert = dynamic_cast<IPKIFNameAndKey*>(&(*curEntry->GetCert()));
                //issuerName = lastCert->Subject();
                if(pathMaxSource < curEntry->GetSource())
                    pathMaxSource = curEntry->GetSource();
            }
            else
            {
                if(curEntry)
                    curEntry->SetIgnore();

                hasCycle = true; //this path has a cycle - try another
                break;
            }
        }

        //move this from here to below the two continue statements to correct counts reported by builder stats
//      ++bs->m_nTotalPathsDiscovered;

#ifdef _DEBUG_PATH_DUMP
        {
            if(!g_pathLogFile.is_open())
            {
                g_pathLogFile.open("_DEBUG_PATH_DUMP_PathLog.txt", ios::out);
            }
            CPKIFCertificatePath dbgpath;
            dbgpath.SetPath(builtPath);
            CPKIFPathLogger pl;
            pl.LogPath(dbgpath, "_DEBUG_PATH_DUMP", &g_pathLogFile);
            if(hasCycle)
                g_pathLogFile << "HasCycle = true" << endl;
            else
                g_pathLogFile << "HasCycle = false" << endl;
        }
#endif

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

        //if we were able to initially complete the table locally and the table has grown
        //we can disregard paths built totally from the local source because they've already been tried
        if(/*basicState->m_bInitCompleteLocal && */pathMaxSource == LOCAL && NULL != basicState->m_reserved)//pathMaxSource < basicState->m_maxSource)
            continue;

        ++bs->m_nTotalPathsDiscovered;

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

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

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

        path.SetTrustRoot(*basicState->m_curRoot);
        path.SetPath(builtPath);

        /*
        CPKIFCertificateNodeList::iterator dbgpos;
        CPKIFCertificateNodeList::iterator dbgend = builtPath.end();
    #ifdef _DEBUG_PATH
        cout << endl << "Returning path from CheckAlternatives..." << endl;
        cout << "Root: " << (*(basicState->m_curRoot))->GetSubjectName()->ToString() << endl;
    #endif
        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((*(basicState->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();
    #ifdef _DEBUG_PATH
            cout << curCertString << " " << (*dbgpos)->GetCert()->SerialNumber() << endl;
    #endif
            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);
}

//----------------------------------------------------------------------------------------------------
//
//  Public interface functions
//
//----------------------------------------------------------------------------------------------------
//This function will build a path to the target specified by the path parameter, using the settings
//specified by the path parameter, using the state specified by the path parameter (as set by previous calls
//to this function).
bool CPKIFPathBuilder2::BuildPath(
                          CPKIFCertificatePath& path)
{ 
    LOG_STRING_DEBUG("CPKIFPathBuilder2::BuildPath(CPKIFCertificatePath& path)", thisComponent, 0, this);

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

    //prepare state - first check to see if state was passed in and if it belongs to us
    CPKIFCertificatePathStatePtr state;
    CPKIFBasicPathState2* basicState = NULL;
    path.GetState(state);

    //if there was state - see if we can cast it to a type that this builder uses
    if(state != (CPKIFCertificatePathState*)NULL)
        basicState = dynamic_cast<CPKIFBasicPathState2* >(&(*state));

    //if there was no state or the cast failed create a new state and put it in the path
    if(NULL == basicState)
    {
        //allocate the new state... (throw bad_alloc)
        basicState = new CPKIFBasicPathState2;      

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

        path.SetBuilderStats(bs);

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

    //----------------------------------------------------------------------------------------------------
    //  PREPARATORY STEPS
    //----------------------------------------------------------------------------------------------------
    //get the target cert as cur cert if path is empty
    CPKIFCertificatePtr curCert;
    CPKIFCertificateNodeList prevPath; 
    path.GetPath(prevPath);

    //see if the previous path is non-empty (i.e. we've been here before)
    if(prevPath.empty())
    {
        //if prevPath is empty, get things ready for the table builder function
        path.GetTarget(curCert);
        if(curCert == (CPKIFCertificate*)NULL)
            RAISE_PATH_EXCEPTION("The path parameter did not specify a target certificate.", thisComponent, COMMON_INVALID_INPUT, this)

        //prepare the list of lists with an entry for the target
        CPKIFCertificateNodeListWithSourceInfoPtr targetList(new CPKIFCertificateNodeListWithSourceInfo);
        CPKIFCertificateNodeEntryPtr tmpNode(new CPKIFCertificateNodeEntry);
        tmpNode->SetCert(curCert);
        targetList->push_back(tmpNode);

        //first entry in the table is always a one node list with the target
        basicState->m_table.clear();
        basicState->m_table.push_back(targetList);

        //check to see if the target is a trust root (if so we can stop building now)
        IPKIFTrustCache* iTrust = GetMediatorFromParent<IPKIFTrustCache>();
        if(NULL == iTrust)
            RAISE_PATH_EXCEPTION("IPKIFTrustCache interface not available.", thisComponent, COMMON_MEDIATOR_MISSING, this)

        IPKIFTrustAnchorList tmpRootList;
        iTrust->GetTrustRoots(curCert->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)
            {
                IPKIFNameAndKey* taNameAndKey = dynamic_cast<IPKIFNameAndKey*>(&(*(*rootPos)));
                IPKIFNameAndKey* certNameAndKey = dynamic_cast<IPKIFNameAndKey*>(&(*curCert));
                if(*certNameAndKey == *taNameAndKey)
                {
                    //if we find a trust root that matches the target then we're done
                    //set the trust root on the path
                    path.SetTrustRoot(*rootPos);

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

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

                    builtPath.push_back(curEntry);
                    path.SetPath(builtPath);
                    basicState->SetTrustRoot(tmpRootList);

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

                    return true;
                }
            }
        }
    }
    else
    {
        //look for any obvious failure causes
        m_impl->SearchForFailure(basicState, prevPath, settings);
    }

    //if the previous path was non-empty or if we set things up (and the target != a trust root)
    //then set the tableComplete bool to false (possibly not true but we'll check for alternatives
    //first) then begin building
    bool tableComplete = false; 
    do
    {
        //----------------------------------------------------------------------------------------------------
        //  INVESTIGATE ALTERNATIVES IN CURRENT TABLE
        //----------------------------------------------------------------------------------------------------
        //check to see if there are any more paths to try amongst any previously returned certs
        if(m_impl->CheckAlternatives(path, basicState))
            return true;

        //----------------------------------------------------------------------------------------------------
        //  BUILD A NEW TABLE OR TRY TO EXPAND IN CURRENT TABLE VIA ADDITIONAL LOCATIONS
        //----------------------------------------------------------------------------------------------------
        tableComplete = m_impl->BuildOrGrowTable(basicState, settings, curCert, prevPath);
        if(!tableComplete && NULL == basicState->m_reserved)
        {
            //if we get here and the table is empty, then the end entity cert was purged.  no need to carry on.
            if(basicState->m_table.empty())
                return false;

            basicState->m_rootList.clear();
            basicState->m_bInitCompleteLocal = false;
            basicState->m_nGrowCount = 0;

            basicState->m_curRoot = NULL;

            basicState->m_maxSource = LOCAL;
            basicState->m_reserved = new char[1];

            CPKIFCertificateNodeListWithSourceInfoPtr targetList(new CPKIFCertificateNodeListWithSourceInfo);
            CPKIFCertificateNodeEntryPtr tmpNode(new CPKIFCertificateNodeEntry);
            path.GetTarget(curCert);
            tmpNode->SetCert(curCert);
            targetList->push_back(tmpNode);

            //first entry in the table is always a one node list with the target
            basicState->m_table.clear();
            basicState->m_table.push_back(targetList);

            tableComplete = m_impl->BuildOrGrowTable(basicState, settings, curCert, prevPath);
        }
    }while(tableComplete);

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