static int build_chain(X509_STORE_CTX *ctx)
{
    SSL_DANE *dane = ctx->dane;
    int num = sk_X509_num(ctx->chain);
    X509 *cert = sk_X509_value(ctx->chain, num - 1);
    int ss = cert_self_signed(cert);
    STACK_OF(X509) *sktmp = NULL;
    unsigned int search;
    int may_trusted = 0;
    int may_alternate = 0;
    int trust = X509_TRUST_UNTRUSTED;
    int alt_untrusted = 0;
    int depth;
    int ok = 0;
    int i;

    /* Our chain starts with a single untrusted element. */
    if (!ossl_assert(num == 1 && ctx->num_untrusted == num))  {
        X509err(X509_F_BUILD_CHAIN, ERR_R_INTERNAL_ERROR);
        ctx->error = X509_V_ERR_UNSPECIFIED;
        return 0;
    }

#define S_DOUNTRUSTED      (1 << 0)     /* Search untrusted chain */
#define S_DOTRUSTED        (1 << 1)     /* Search trusted store */
#define S_DOALTERNATE      (1 << 2)     /* Retry with pruned alternate chain */
    /*
     * Set up search policy, untrusted if possible, trusted-first if enabled.
     * If we're doing DANE and not doing PKIX-TA/PKIX-EE, we never look in the
     * trust_store, otherwise we might look there first.  If not trusted-first,
     * and alternate chains are not disabled, try building an alternate chain
     * if no luck with untrusted first.
     */
    search = (ctx->untrusted != NULL) ? S_DOUNTRUSTED : 0;
    if (DANETLS_HAS_PKIX(dane) || !DANETLS_HAS_DANE(dane)) {
        if (search == 0 || ctx->param->flags & X509_V_FLAG_TRUSTED_FIRST)
            search |= S_DOTRUSTED;
        else if (!(ctx->param->flags & X509_V_FLAG_NO_ALT_CHAINS))
            may_alternate = 1;
        may_trusted = 1;
    }

    /*
     * Shallow-copy the stack of untrusted certificates (with TLS, this is
     * typically the content of the peer's certificate message) so can make
     * multiple passes over it, while free to remove elements as we go.
     */
    if (ctx->untrusted && (sktmp = sk_X509_dup(ctx->untrusted)) == NULL) {
        X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
        ctx->error = X509_V_ERR_OUT_OF_MEM;
        return 0;
    }

    /*
     * If we got any "DANE-TA(2) Cert(0) Full(0)" trust-anchors from DNS, add
     * them to our working copy of the untrusted certificate stack.  Since the
     * caller of X509_STORE_CTX_init() may have provided only a leaf cert with
     * no corresponding stack of untrusted certificates, we may need to create
     * an empty stack first.  [ At present only the ssl library provides DANE
     * support, and ssl_verify_cert_chain() always provides a non-null stack
     * containing at least the leaf certificate, but we must be prepared for
     * this to change. ]
     */
    if (DANETLS_ENABLED(dane) && dane->certs != NULL) {
        if (sktmp == NULL && (sktmp = sk_X509_new_null()) == NULL) {
            X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
            ctx->error = X509_V_ERR_OUT_OF_MEM;
            return 0;
        }
        for (i = 0; i < sk_X509_num(dane->certs); ++i) {
            if (!sk_X509_push(sktmp, sk_X509_value(dane->certs, i))) {
                sk_X509_free(sktmp);
                X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
                ctx->error = X509_V_ERR_OUT_OF_MEM;
                return 0;
            }
        }
    }

    /*
     * Still absurdly large, but arithmetically safe, a lower hard upper bound
     * might be reasonable.
     */
    if (ctx->param->depth > INT_MAX/2)
        ctx->param->depth = INT_MAX/2;

    /*
     * Try to Extend the chain until we reach an ultimately trusted issuer.
     * Build chains up to one longer the limit, later fail if we hit the limit,
     * with an X509_V_ERR_CERT_CHAIN_TOO_LONG error code.
     */
    depth = ctx->param->depth + 1;

    while (search != 0) {
        X509 *x;
        X509 *xtmp = NULL;

        /*
         * Look in the trust store if enabled for first lookup, or we've run
         * out of untrusted issuers and search here is not disabled.  When we
         * reach the depth limit, we stop extending the chain, if by that point
         * we've not found a trust-anchor, any trusted chain would be too long.
         *
         * The error reported to the application verify callback is at the
         * maximal valid depth with the current certificate equal to the last
         * not ultimately-trusted issuer.  For example, with verify_depth = 0,
         * the callback will report errors at depth=1 when the immediate issuer
         * of the leaf certificate is not a trust anchor.  No attempt will be
         * made to locate an issuer for that certificate, since such a chain
         * would be a-priori too long.
         */
        if ((search & S_DOTRUSTED) != 0) {
            i = num = sk_X509_num(ctx->chain);
            if ((search & S_DOALTERNATE) != 0) {
                /*
                 * As high up the chain as we can, look for an alternative
                 * trusted issuer of an untrusted certificate that currently
                 * has an untrusted issuer.  We use the alt_untrusted variable
                 * to track how far up the chain we find the first match.  It
                 * is only if and when we find a match, that we prune the chain
                 * and reset ctx->num_untrusted to the reduced count of
                 * untrusted certificates.  While we're searching for such a
                 * match (which may never be found), it is neither safe nor
                 * wise to preemptively modify either the chain or
                 * ctx->num_untrusted.
                 *
                 * Note, like ctx->num_untrusted, alt_untrusted is a count of
                 * untrusted certificates, not a "depth".
                 */
                i = alt_untrusted;
            }
            x = sk_X509_value(ctx->chain, i-1);

            ok = (depth < num) ? 0 : get_issuer(&xtmp, ctx, x);

            if (ok < 0) {
                trust = X509_TRUST_REJECTED;
                ctx->error = X509_V_ERR_STORE_LOOKUP;
                search = 0;
                continue;
            }

            if (ok > 0) {
                /*
                 * Alternative trusted issuer for a mid-chain untrusted cert?
                 * Pop the untrusted cert's successors and retry.  We might now
                 * be able to complete a valid chain via the trust store.  Note
                 * that despite the current trust-store match we might still
                 * fail complete the chain to a suitable trust-anchor, in which
                 * case we may prune some more untrusted certificates and try
                 * again.  Thus the S_DOALTERNATE bit may yet be turned on
                 * again with an even shorter untrusted chain!
                 *
                 * If in the process we threw away our matching PKIX-TA trust
                 * anchor, reset DANE trust.  We might find a suitable trusted
                 * certificate among the ones from the trust store.
                 */
                if ((search & S_DOALTERNATE) != 0) {
                    if (!ossl_assert(num > i && i > 0 && ss == 0)) {
                        X509err(X509_F_BUILD_CHAIN, ERR_R_INTERNAL_ERROR);
                        X509_free(xtmp);
                        trust = X509_TRUST_REJECTED;
                        ctx->error = X509_V_ERR_UNSPECIFIED;
                        search = 0;
                        continue;
                    }
                    search &= ~S_DOALTERNATE;
                    for (; num > i; --num)
                        X509_free(sk_X509_pop(ctx->chain));
                    ctx->num_untrusted = num;

                    if (DANETLS_ENABLED(dane) &&
                        dane->mdpth >= ctx->num_untrusted) {
                        dane->mdpth = -1;
                        X509_free(dane->mcert);
                        dane->mcert = NULL;
                    }
                    if (DANETLS_ENABLED(dane) &&
                        dane->pdpth >= ctx->num_untrusted)
                        dane->pdpth = -1;
                }

                /*
                 * Self-signed untrusted certificates get replaced by their
                 * trusted matching issuer.  Otherwise, grow the chain.
                 */
                if (ss == 0) {
                    if (!sk_X509_push(ctx->chain, x = xtmp)) {
                        X509_free(xtmp);
                        X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
                        trust = X509_TRUST_REJECTED;
                        ctx->error = X509_V_ERR_OUT_OF_MEM;
                        search = 0;
                        continue;
                    }
                    ss = cert_self_signed(x);
                } else if (num == ctx->num_untrusted) {
                    /*
                     * We have a self-signed certificate that has the same
                     * subject name (and perhaps keyid and/or serial number) as
                     * a trust-anchor.  We must have an exact match to avoid
                     * possible impersonation via key substitution etc.
                     */
                    if (X509_cmp(x, xtmp) != 0) {
                        /* Self-signed untrusted mimic. */
                        X509_free(xtmp);
                        ok = 0;
                    } else {
                        X509_free(x);
                        ctx->num_untrusted = --num;
                        (void) sk_X509_set(ctx->chain, num, x = xtmp);
                    }
                }

                /*
                 * We've added a new trusted certificate to the chain, recheck
                 * trust.  If not done, and not self-signed look deeper.
                 * Whether or not we're doing "trusted first", we no longer
                 * look for untrusted certificates from the peer's chain.
                 *
                 * At this point ctx->num_trusted and num must reflect the
                 * correct number of untrusted certificates, since the DANE
                 * logic in check_trust() depends on distinguishing CAs from
                 * "the wire" from CAs from the trust store.  In particular, the
                 * certificate at depth "num" should be the new trusted
                 * certificate with ctx->num_untrusted <= num.
                 */
                if (ok) {
                    if (!ossl_assert(ctx->num_untrusted <= num)) {
                        X509err(X509_F_BUILD_CHAIN, ERR_R_INTERNAL_ERROR);
                        trust = X509_TRUST_REJECTED;
                        ctx->error = X509_V_ERR_UNSPECIFIED;
                        search = 0;
                        continue;
                    }
                    search &= ~S_DOUNTRUSTED;
                    switch (trust = check_trust(ctx, num)) {
                    case X509_TRUST_TRUSTED:
                    case X509_TRUST_REJECTED:
                        search = 0;
                        continue;
                    }
                    if (ss == 0)
                        continue;
                }
            }

            /*
             * No dispositive decision, and either self-signed or no match, if
             * we were doing untrusted-first, and alt-chains are not disabled,
             * do that, by repeatedly losing one untrusted element at a time,
             * and trying to extend the shorted chain.
             */
            if ((search & S_DOUNTRUSTED) == 0) {
                /* Continue search for a trusted issuer of a shorter chain? */
                if ((search & S_DOALTERNATE) != 0 && --alt_untrusted > 0)
                    continue;
                /* Still no luck and no fallbacks left? */
                if (!may_alternate || (search & S_DOALTERNATE) != 0 ||
                    ctx->num_untrusted < 2)
                    break;
                /* Search for a trusted issuer of a shorter chain */
                search |= S_DOALTERNATE;
                alt_untrusted = ctx->num_untrusted - 1;
                ss = 0;
            }
        }

        /*
         * Extend chain with peer-provided certificates
         */
        if ((search & S_DOUNTRUSTED) != 0) {
            num = sk_X509_num(ctx->chain);
            if (!ossl_assert(num == ctx->num_untrusted)) {
                X509err(X509_F_BUILD_CHAIN, ERR_R_INTERNAL_ERROR);
                trust = X509_TRUST_REJECTED;
                ctx->error = X509_V_ERR_UNSPECIFIED;
                search = 0;
                continue;
            }
            x = sk_X509_value(ctx->chain, num-1);

            /*
             * Once we run out of untrusted issuers, we stop looking for more
             * and start looking only in the trust store if enabled.
             */
            xtmp = (ss || depth < num) ? NULL : find_issuer(ctx, sktmp, x);
            if (xtmp == NULL) {
                search &= ~S_DOUNTRUSTED;
                if (may_trusted)
                    search |= S_DOTRUSTED;
                continue;
            }

            /* Drop this issuer from future consideration */
            (void) sk_X509_delete_ptr(sktmp, xtmp);

            if (!X509_up_ref(xtmp)) {
                X509err(X509_F_BUILD_CHAIN, ERR_R_INTERNAL_ERROR);
                trust = X509_TRUST_REJECTED;
                ctx->error = X509_V_ERR_UNSPECIFIED;
                search = 0;
                continue;
            }

            if (!sk_X509_push(ctx->chain, xtmp)) {
                X509_free(xtmp);
                X509err(X509_F_BUILD_CHAIN, ERR_R_MALLOC_FAILURE);
                trust = X509_TRUST_REJECTED;
                ctx->error = X509_V_ERR_OUT_OF_MEM;
                search = 0;
                continue;
            }

            x = xtmp;
            ++ctx->num_untrusted;
            ss = cert_self_signed(xtmp);

            /*
             * Check for DANE-TA trust of the topmost untrusted certificate.
             */
            switch (trust = check_dane_issuer(ctx, ctx->num_untrusted - 1)) {
            case X509_TRUST_TRUSTED:
            case X509_TRUST_REJECTED:
                search = 0;
                continue;
            }
        }
    }
    sk_X509_free(sktmp);

    /*
     * Last chance to make a trusted chain, either bare DANE-TA public-key
     * signers, or else direct leaf PKIX trust.
     */
    num = sk_X509_num(ctx->chain);
    if (num <= depth) {
        if (trust == X509_TRUST_UNTRUSTED && DANETLS_HAS_DANE_TA(dane))
            trust = check_dane_pkeys(ctx);
        if (trust == X509_TRUST_UNTRUSTED && num == ctx->num_untrusted)
            trust = check_trust(ctx, num);
    }

    switch (trust) {
    case X509_TRUST_TRUSTED:
        return 1;
    case X509_TRUST_REJECTED:
        /* Callback already issued */
        return 0;
    case X509_TRUST_UNTRUSTED:
    default:
        num = sk_X509_num(ctx->chain);
        if (num > depth)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_CERT_CHAIN_TOO_LONG);
        if (DANETLS_ENABLED(dane) &&
            (!DANETLS_HAS_PKIX(dane) || dane->pdpth >= 0))
            return verify_cb_cert(ctx, NULL, num-1, X509_V_ERR_DANE_NO_MATCH);
        if (ss && sk_X509_num(ctx->chain) == 1)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_DEPTH_ZERO_SELF_SIGNED_CERT);
        if (ss)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_SELF_SIGNED_CERT_IN_CHAIN);
        if (ctx->num_untrusted < num)
            return verify_cb_cert(ctx, NULL, num-1,
                                  X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT);
        return verify_cb_cert(ctx, NULL, num-1,
                              X509_V_ERR_UNABLE_TO_GET_ISSUER_CERT_LOCALLY);
    }
}