// merkle.rue by yakuhito

import tree_hash::{tree_hash_atom, tree_hash_pair};

export struct MerkleProof {
    path: Int,
    ...hashes: List<Bytes32>,
}

export fn calculate_merkle_root(
    path: Int,
    current_hash: Bytes32,
    additional_steps: List<Bytes32>,
) -> Bytes32 {
    if additional_steps is nil {
        return current_hash;
    }
    
    calculate_merkle_root(
        path >>> 1,
        tree_hash_pair(
            inline if path & 1 != 0 {
                additional_steps.first
            } else {
                current_hash
            },
            inline if path & 1 != 0 {
                current_hash
            } else {
                additional_steps.first
            }
        ),
        additional_steps.rest
    )
}

fn simplify_merkle_proof_after_leaf(
    leaf_hash: Bytes32,
    proof: MerkleProof,
) -> Bytes32 {
    if proof.hashes is nil {
        return leaf_hash;
    }

    simplify_merkle_proof_after_leaf(
        tree_hash_pair(
            inline if proof.path & 1 != 0 {
                proof.hashes.first
            } else {
                leaf_hash
            },
            inline if proof.path & 1 != 0 {
                leaf_hash
            } else {
                proof.hashes.first
            }
        ),
        MerkleProof {
            path: proof.path >>> 1,
            hashes: proof.hashes.rest
        }
    )
}

export inline fn simplify_merkle_proof(
    leaf: Bytes32,
    proof: MerkleProof,
) -> Bytes32 {
    simplify_merkle_proof_after_leaf(tree_hash_atom(leaf), proof)
}
