import { PublicKey } from '@dxos/keys';
import { type Credential } from '@dxos/protocols/proto/dxos/halo/credentials';
import { type AsyncCallback, Callback, ComplexMap, ComplexSet } from '@dxos/util';
export declare class CredentialGraph<A, State> {
    private readonly _stateHandler;
    /**
     * Local ids are used during traversals.
     */
    private _vertexIdGenerator;
    /**
     * All credentials without parent references are connected to the root.
     */
    private _root;
    /**
     * A credential which is not a parent of any other credential has the sentinel as a child.
     * Sentinel is a virtual merge-point of all credentials.
     */
    private _sentinel;
    /**
     * Vertex references are used for fast credential inserts into the graph.
     */
    private _vertexByCredentialId;
    /**
     * The current state of the graph.
     */
    private _subjectToVertex;
    private _subjectToState;
    onSubjectStateChanged: Callback<AsyncCallback<State[]>>;
    constructor(_stateHandler: CredentialGraphStateHandler<A, State>);
    getSubjectState(subjectId: PublicKey): State | undefined;
    getState(): ReadonlyMap<PublicKey, State>;
    getLeafIds(): PublicKey[];
    getGlobalStateScope(): StateScope<A>;
    addVertex(credential: Credential, assertion: A): Promise<void>;
    private _removeSentinelConnection;
    private _onVertexInserted;
    /**
     * DFS the graph from root to sentinel pausing on merge points (nodes with multiple parents).
     * Continue after all paths leading to a merge point converge by merging their states.
     * In case of a concurrent update paths are replayed taking into account the state set
     * by the winning branch.
     */
    private _recomputeState;
    private _replayFailedPaths;
    private _handleMergePoint;
    private _updatePathState;
    private _forkTraversal;
    /**
     * Updates the current graph state.
     * @returns changed states.
     */
    private _setCurrentState;
    private _leastCommonAncestor;
    /**
     * We might be merging paths where some of them had fork points after the initial forking.
     * We need all the paths to point to the least common fork point and contain all the changes
     * that happened after it.
     */
    private _moveUpToForkPoint;
    private _mergePaths;
    /**
     * A candidate credential is preferred over the existing credential if:
     *  1. It is the merge-point, because it's the last credential that was issued in awareness of all
     *  the previously existing ones.
     *  2. A path where candidate was set contains existing credential in it, which means that the candidate
     *  was issued after the existing credential by a legitimate issuer.
     *  3. A state-specific logic (_stateHandler) is able to justify using the candidate credential.
     *  4. The path where candidate was set has more issuers than the existing path (longer branch).
     *  5. The issuance time of the candidate is after the issuance time of the existing credential (LWW).
     */
    private _shouldOverrideCredential;
    private _createRootPath;
}
export interface StateScope<A> {
    head?: {
        id: number;
    };
    state: ReadonlyMap<PublicKey, ChainVertex<A>>;
    stateOverrides?: ReadonlyMap<PublicKey, ChainVertex<A>>;
}
export interface CredentialGraphStateHandler<Assertion, State> {
    hasStateChanged(s1?: State, s2?: State): boolean;
    createState(credential: Credential, assertion: Assertion): State;
    isUpdateAllowed: (scope: StateScope<Assertion>, update: Credential, assertion: Assertion) => boolean;
    getConflictingPaths(paths: PathState<Assertion>[], update: ChainVertex<Assertion>): PathState<Assertion>[];
    tryPickWinningUpdate(scope1: StateScope<Assertion>, update1: Credential, scope2: StateScope<Assertion>, update2: Credential): Credential | null;
    toLogString(assertion: Assertion): string;
}
export interface PathState<A> {
    /**
     * The current vertex position in path, always advances.
     */
    head: ChainVertex<A>;
    /**
     * Subject info local to the current path.
     */
    state: ComplexMap<PublicKey, ChainVertex<A>>;
    /**
     * Used during path replay to throw away cascading concurrent modifications.
     * Overrides pathState.
     */
    stateOverrides?: ComplexMap<PublicKey, ChainVertex<A>>;
    /**
     * Used to faster search of conflicting branches. Is different from pathState.keys()
     * because pathState is not reset on forks.
     */
    forkChangedSubjects: ComplexSet<PublicKey>;
    /**
     * Used to find winning branches. A branch wins if it had more participants.
     * Ties are broken using credential issuance date.
     */
    forkIssuers: ComplexSet<PublicKey>;
    /**
     * All the credentials processed during this path traversal.
     */
    credentials: ComplexSet<PublicKey>;
    /**
     * PathState where we had multiple children in the current vertex.
     * Will be merged with child branches when they converge.
     */
    forkPoint?: PathState<A>;
    /**
     * Used for a particular path replay with stateOverrides for conflict resolution
     * forkVertexId is mapped to child vertex selection.
     * Contains choices that lead to the current state. Value is an array when
     * some branches converged before converging with the remaining branches.
     */
    chosenPath: {
        [forkVertexId: number]: ChainVertex<A>[];
    };
}
export interface ChainVertex<Assertion> {
    /**
     * The field is missing on root and sentinel vertices. Assertion is not undefined to avoid
     * always asserting two fields.
     */
    credential?: Credential;
    assertion: Assertion;
    /**
     * Local incrementing counter used to form paths. Is used only for causality resolution.
     */
    id: number;
    /**
     * Parents references are used to handle divergent branch merge-points.
     */
    parents: ChainVertex<Assertion>[];
    /**
     * Child references are traversed when computing the current state.
     */
    children: ChainVertex<Assertion>[];
}
//# sourceMappingURL=credential-graph.d.ts.map