//! Bounded comparison of type contracts from separate RIL programs.

@test export mod tests;

use std::lang::il;
use std::mem::heap;

/// Largest comparison workspace accepted by the graph matcher.
export constant MAX_PAIRS: u32 = 65536;

/// Multiplier for the left descriptor index in a pair hash.
constant HASH_LEFT: u64 = 0x9e3779b1;
/// Multiplier for the right descriptor index in a pair hash.
constant HASH_RIGHT: u64 = 0x85ebca77;

/// A graph comparison exceeded its capacity or could not allocate storage.
export union Error: Copy {
    /// The number of distinct descriptor pairs exceeds the configured limit.
    Limit,
    /// The scratch heap has insufficient storage.
    Storage,
}

/// Descriptor table selected by a graph edge.
union Kind: Copy {
    /// Object representation and its protected slots.
    Layout,
    /// Function parameters, result, and borrow relations.
    Signature,
    /// Ordered method contracts and receiver rights.
    Trait,
}

/// One distinct pair of descriptors and its occupied hash-table slot.
record Pair: Copy {
    /// Descriptor table.
    kind: Kind,
    /// Index in the left program.
    left: u32,
    /// Index in the right program.
    right: u32,
    /// Slot which indexes this pair in Workspace.slots.
    bucket: u32,
}

/// Reusable storage for comparison of cyclic descriptor graphs.
export opaque record Workspace {
    /// Distinct pairs, in discovery order. Its length is the pair limit.
    pairs: *mut [Pair],
    /// Open-addressed pair indices plus one; zero denotes an empty slot.
    slots: *mut [u32],
    /// Initialized prefix of pairs.
    count: u32,
}

/// Allocate a bounded workspace. The heap must outlive all comparisons with it.
export fn workspace(limit: u32, arena: &heap::Heap) -> Workspace throws (Error) {
    if limit == 0 or limit > MAX_PAIRS {
        throw Error::Limit;
    }
    let mut size: u32 = 2;
    while size < limit * 2 {
        set size *= 2;
    }
    let mut slots: *mut [u32] = &mut [];
    let mut pairs: *mut [Pair] = &mut [];
    try slots.resize(size, 0, arena) catch {
        throw Error::Storage;
    };
    try pairs.resize(
        limit, Pair { kind: Kind::Layout, left: 0, right: 0, bucket: 0 }, arena
    ) catch {
        throw Error::Storage;
    };
    return Workspace { pairs, slots, count: 0 };
}

/// Clear the slots used by the previous comparison.
fn reset(work: &mut Workspace) {
    for pair in &work.pairs[.. work.count] {
        set work.slots[pair.bucket] = 0;
    }
    set work.count = 0;
}

/// Add an unseen edge. Existing pairs terminate traversal of a cycle.
fn edge(work: &mut Workspace, kind: Kind, left: u32, right: u32) throws (Error) {
    let mut tag: u64 = 0;
    match kind {
        case Kind::Layout    => set tag = 1,
        case Kind::Signature => set tag = 2,
        case Kind::Trait     => set tag = 3,
    }
    let hash = ((left as u64 * HASH_LEFT) ^ (right as u64 * HASH_RIGHT) ^ tag) as u32;
    let mask = work.slots.len - 1;
    let mut bucket = hash & mask;
    loop {
        let index = work.slots[bucket];
        if index == 0 {
            if work.count == work.pairs.len {
                throw Error::Limit;
            }
            set work.pairs[work.count] = Pair { kind, left, right, bucket };
            set work.count += 1;
            set work.slots[bucket] = work.count;
            return;
        }
        let pair = work.pairs[index - 1];
        if pair.kind == kind and pair.left == left and pair.right == right {
            return;
        }
        set bucket = (bucket + 1) & mask;
    }
}

/// Match pointer rights and enqueue the pointee layouts.
fn pointer(work: &mut Workspace, left: il::PtrType, right: il::PtrType) -> bool throws (Error) {
    if left.own <> right.own or left.mutable <> right.mutable or left.nullable <> right.nullable {
        return false;
    }
    try edge(work, Kind::Layout, left.layout, right.layout);
    return true;
}

/// Match a value type and enqueue its descriptor edges.
fn value(work: &mut Workspace, left: il::ValType, right: il::ValType) -> bool throws (Error) {
    match left {
        case il::ValType::Void => {
            if let case il::ValType::Void = right {
                return true;
            }
        }
        case il::ValType::Data(a) => {
            if let case il::ValType::Data(b) = right {
                return a == b;
            }
        }
        case il::ValType::Ptr(a) => {
            if let case il::ValType::Ptr(b) = right {
                return try pointer(work, a, b);
            }
        }
        case il::ValType::Fn(a) => {
            if let case il::ValType::Fn(b) = right {
                try edge(work, Kind::Signature, a, b);
                return true;
            }
        }
        case il::ValType::Heap(a) => {
            if let case il::ValType::Heap(b) = right {
                return a == b;
            }
        }
    }
    return false;
}

/// Match region positions, which determine the meaning of borrow contracts.
fn regions(left: &[u32], right: &[u32]) -> bool {
    if left.len <> right.len {
        return false;
    }
    for item, i in left {
        if item <> right[i] {
            return false;
        }
    }
    return true;
}

/// Match a protected slot and enqueue every referenced descriptor.
fn slot(work: &mut Workspace, left: il::SlotKind, right: il::SlotKind) -> bool throws (Error) {
    match left {
        case il::SlotKind::Ptr(a) => {
            if let case il::SlotKind::Ptr(b) = right {
                return try pointer(work, a, b);
            }
        }
        case il::SlotKind::Slice(a) => {
            if let case il::SlotKind::Slice(b) = right {
                return try pointer(work, a, b);
            }
        }
        case il::SlotKind::Fn(a) => {
            if let case il::SlotKind::Fn(b) = right {
                try edge(work, Kind::Signature, a, b);
                return true;
            }
        }
        case il::SlotKind::Heap(a) => {
            if let case il::SlotKind::Heap(b) = right {
                return a == b;
            }
        }
        case il::SlotKind::Trait(a) => {
            if let case il::SlotKind::Trait(b) = right {
                if a.own <> b.own or a.mutable <> b.mutable {
                    return false;
                }
                try edge(work, Kind::Trait, a.iface, b.iface);
                return true;
            }
        }
        case il::SlotKind::Sub(a) => {
            if let case il::SlotKind::Sub(b) = right {
                try edge(work, Kind::Layout, a, b);
                return true;
            }
        }
        case il::SlotKind::Array { layout: a, count: countA } => {
            if let case il::SlotKind::Array { layout: b, count: countB } = right {
                if countA <> countB {
                    return false;
                }
                try edge(work, Kind::Layout, a, b);
                return true;
            }
        }
        case il::SlotKind::Union { offset: offsetA, size: sizeA, variants: a } => {
            if let case il::SlotKind::Union { offset: offsetB, size: sizeB, variants: b } = right {
                if offsetA <> offsetB or sizeA <> sizeB or a.len <> b.len {
                    return false;
                }
                for variant, i in a {
                    if variant.tag <> b[i].tag or not regions(variant.regions, b[i].regions) {
                        return false;
                    }
                    if let child = variant.layout {
                        let other = b[i].layout else {
                            return false;
                        };
                        try edge(work, Kind::Layout, child, other);
                    } else if b[i].layout <> nil {
                        return false;
                    }
                }
                return true;
            }
        }
    }
    return false;
}

/// Check every reachable pair. Invalid table indices are mismatches.
fn finish(work: &mut Workspace, left: &il::Program, right: &il::Program) -> bool throws (Error) {
    let mut cursor: u32 = 0;
    while cursor < work.count {
        let pair = work.pairs[cursor];
        set cursor += 1;
        match pair.kind {
            case Kind::Layout => {
                if pair.left >= left.layouts.len or pair.right >= right.layouts.len {
                    return false;
                }
                let a = left.layouts[pair.left];
                let b = right.layouts[pair.right];
                if a.size <> b.size
                    or a.alignment <> b.alignment
                    or a.regions <> b.regions
                    or a.slots.len <> b.slots.len
                {
                    return false;
                }
                for item, i in a.slots {
                    let other = b.slots[i];
                    if item.offset <> other.offset
                        or not regions(item.regions, other.regions)
                        or not try slot(work, item.kind, other.kind)
                    {
                        return false;
                    }
                }
            }
            case Kind::Signature => {
                if pair.left >= left.signatures.len or pair.right >= right.signatures.len {
                    return false;
                }
                let a = left.signatures[pair.left];
                let b = right.signatures[pair.right];
                if a.params.len <> b.params.len
                    or not il::sameBorrows(a.borrows, b.borrows)
                    or not try value(work, a.ret, b.ret)
                {
                    return false;
                }
                for param, i in a.params {
                    if not try value(work, param, b.params[i]) {
                        return false;
                    }
                }
            }
            case Kind::Trait => {
                if pair.left >= left.traits.len or pair.right >= right.traits.len {
                    return false;
                }
                let a = left.traits[pair.left];
                let b = right.traits[pair.right];
                if a.methods.len <> b.methods.len {
                    return false;
                }
                for method, i in a.methods {
                    let other = b.methods[i];
                    if method.receiver <> other.receiver
                        or method.own <> other.own
                        or method.mutable <> other.mutable
                    {
                        return false;
                    }
                    try edge(work, Kind::Signature, method.sig, other.sig);
                }
            }
        }
    }
    return true;
}

/// Compare complete layout graphs across program-local indices.
export fn sameLayout(
    work: &mut Workspace, left: &il::Program, a: u32, right: &il::Program, b: u32
) -> bool throws (Error) {
    reset(work);
    try edge(work, Kind::Layout, a, b);
    return try finish(work, left, right);
}

/// Compare data declarations and their reachable layout graphs.
export fn sameData(
    work: &mut Workspace, left: &il::Program, a: &il::Data, right: &il::Program, b: &il::Data
) -> bool throws (Error) {
    if a.size <> b.size
        or a.alignment <> b.alignment
        or a.readOnly <> b.readOnly
        or a.heap <> b.heap
    {
        return false;
    }
    return try sameLayout(work, left, a.layout, right, b.layout);
}

/// Compare an importing signature with a provider's declared function.
export fn sameCallable(
    work: &mut Workspace, left: &il::Program, a: &il::Signature, right: &il::Program, b: &il::Fn
) -> bool throws (Error) {
    reset(work);
    if a.params.len <> b.params.len
        or not il::sameBorrows(a.borrows, b.borrows)
        or not try value(work, a.ret, b.returnType)
    {
        return false;
    }
    for param, i in a.params {
        if not try value(work, param, b.params[i].type) {
            return false;
        }
    }
    return try finish(work, left, right);
}
