resolver.reef - zygaena/coral

root / src / core / resolver.reef
resolver.reef Reef 757 lines 24.9 KB
/******************************************************************************
               __               ____                __
              / /   ___  ____ _/ __/_____________ _/ /__
             / /   / _ \/ __ `/ /_/ ___/ ___/ __ `/ / _ \
            / /___/  __/ /_/ / __(__  ) /__/ /_/ / /  __/
           /_____/\___/\__,_/_/ /____/\___/\__,_/_/\___/

   (C)opyright 2025, Leafscale, LLC -  https://www.leafscale.com

   Project: Zygaena
  Filename: resolver.reef
   Authors: Chris Tusa <chris.tusa@leafscale.com>
   License: <see LICENSE file included with this source code>
Description: Dependency resolution for package installation

******************************************************************************/

module core.resolver

import core.str
import io.file
import io.path
import types
import core.port
import core.database
import util.version as ver

export
    type ResolveResult

    fn resolve(name: string): ResolveResult
    fn get_install_order(names: [string], name_count: int, result: [string], max_count: int): int
    fn get_dep_tree(name: string, deps: [string], max_count: int): int

    // Build dependency resolver (resolves both runtime + build deps recursively from source)
    fn resolve_build_deps(name: string): ResolveResult

    // Root-aware version for alternate root installation
    fn get_install_order_rooted(names: [string], name_count: int, result: [string], max_count: int, root: string): int
end export

// Result for alternative resolution
type AlternativeChoice = struct
    satisfied: bool       // True if an alternative is already installed
    provider: string      // The installed provider (if satisfied)
    options: [string]     // Available options to choose from
    option_count: int
    base_dep: string      // The base dependency name
end AlternativeChoice

// Resolution result
type ResolveResult = struct
    success: bool
    packages: [string]
    count: int
    error: string
end ResolveResult

// Create an empty result
fn new_result(): ResolveResult
    mut packages: [string] = new [string](256)
    return ResolveResult{ success: false, packages: packages, count: 0, error: "" }
end new_result

// Resolve dependencies for a package
// Returns ordered list of packages to install (dependencies first)
fn resolve(name: string): ResolveResult
    mut result = new_result()

    // Track visited to detect cycles
    mut visited: [string] = new [string](256)
    mut visited_count = 0

    // Track resolution order
    mut order: [string] = new [string](256)
    mut order_count = 0

    // Resolve recursively
    let ok = resolve_recursive(name, visited, visited_count, order, order_count)

    if not ok.success
        result.error = ok.error
        return result
    end if

    result.success = true
    result.packages = ok.packages
    result.count = ok.count
    return result
end resolve

// Internal result for recursive resolution
type RecurseResult = struct
    success: bool
    packages: [string]
    count: int
    error: string
end RecurseResult

fn new_recurse_result(): RecurseResult
    mut packages: [string] = new [string](256)
    return RecurseResult{ success: true, packages: packages, count: 0, error: "" }
end new_recurse_result

fn resolve_recursive(name: string, visited: [string], visited_count: int, order: [string], order_count: int): RecurseResult
    mut result = new_recurse_result()
    result.packages = order
    result.count = order_count

    // Check for cycle
    if array_contains(visited, visited_count, name)
        // Already visited - skip
        result.success = true
        return result
    end if

    // Mark as visited
    visited[visited_count] = name
    let new_visited_count = visited_count + 1

    // Find the port
    let port_result = port.find(name)
    if not port_result.success
        // Check if already installed
        if database.is_installed(name)
            result.success = true
            return result
        end if

        // Check if an alternative provider exists
        let provider = database.find_provider(name)
        if str.length(provider) > 0
            // Alternative already installed
            result.success = true
            return result
        end if

        result.success = false
        result.error = "Port not found: " + name
        return result
    end if

    let p = port_result.port
    let pkg_name = p.info.name

    // Resolve runtime dependencies first
    mut i = 0
    while i < p.deps.runtime_count
        let dep = p.deps.runtime[i]

        // Check if this is an alternative dependency
        if is_alternative_dep(dep)
            let alt_choice = resolve_alternative(dep)

            if alt_choice.satisfied
                // An alternative is already installed, skip
                i = i + 1
                continue
            end if

            // No alternative installed - pick the first option
            // In a full implementation, we'd prompt the user here
            if alt_choice.option_count > 0
                let chosen = alt_choice.options[0]
                if not array_contains(result.packages, result.count, chosen)
                    let dep_result = resolve_recursive(chosen, visited, new_visited_count, result.packages, result.count)
                    if not dep_result.success
                        return dep_result
                    end if
                    result.packages = dep_result.packages
                    result.count = dep_result.count
                end if
            end if
        else
            // Regular dependency — may include version constraint (e.g., "libfoo>=1.0")
            let constraint = ver.parse_dep_constraint(dep)
            let dep_name = ver.constraint_name(constraint)

            if database.is_installed(dep_name)
                // Installed — check version constraint if present
                if ver.has_constraint(constraint)
                    let installed_pkg = database.get_installed(dep_name)
                    if not ver.check_version_constraint(installed_pkg.info.version, ver.constraint_op(constraint), ver.constraint_version(constraint))
                        // Installed version doesn't satisfy constraint — needs upgrade
                        if not array_contains(result.packages, result.count, dep_name)
                            let dep_result = resolve_recursive(dep_name, visited, new_visited_count, result.packages, result.count)
                            if not dep_result.success
                                return dep_result
                            end if
                            result.packages = dep_result.packages
                            result.count = dep_result.count
                        end if
                    end if
                end if
                // No constraint or constraint satisfied — skip
            else
                // Not installed — resolve it
                if not array_contains(result.packages, result.count, dep_name)
                    let dep_result = resolve_recursive(dep_name, visited, new_visited_count, result.packages, result.count)
                    if not dep_result.success
                        return dep_result
                    end if
                    result.packages = dep_result.packages
                    result.count = dep_result.count
                end if
            end if
        end if

        i = i + 1
    end while

    // Add this package to order (after its dependencies)
    // Use canonical name from package.toml, not the raw search argument
    if not array_contains(result.packages, result.count, pkg_name)
        // Skip if already installed
        if not database.is_installed(pkg_name)
            result.packages[result.count] = pkg_name
            result.count = result.count + 1
        end if
    end if

    result.success = true
    return result
end resolve_recursive

// Get install order for multiple packages
fn get_install_order(names: [string], name_count: int, result: [string], max_count: int): int
    mut order_count = 0

    mut i = 0
    while i < name_count
        let name = names[i]
        let resolve_result = resolve(name)

        if resolve_result.success
            // Add resolved packages to result
            mut j = 0
            while j < resolve_result.count and order_count < max_count
                let pkg = resolve_result.packages[j]
                // Avoid duplicates
                if not array_contains(result, order_count, pkg)
                    result[order_count] = pkg
                    order_count = order_count + 1
                end if
                j = j + 1
            end while
        end if

        i = i + 1
    end while

    return order_count
end get_install_order

// Get dependency tree for display (with indentation info)
fn get_dep_tree(name: string, deps: [string], max_count: int): int
    mut count = 0
    collect_deps(name, deps, count, 0, max_count)
    return count
end get_dep_tree

// Collect dependencies recursively
fn collect_deps(name: string, deps: [string], count: int, depth: int, max_count: int): int
    if depth > 20 or count >= max_count
        return count
    end if

    let result = port.find(name)
    if not result.success
        return count
    end if

    let p = result.port
    mut current_count = count

    mut i = 0
    while i < p.deps.runtime_count and current_count < max_count
        let dep = p.deps.runtime[i]

        // Add with depth prefix (number of spaces = depth * 2)
        let indent = make_indent(depth)
        deps[current_count] = indent + dep
        current_count = current_count + 1

        // Recurse
        current_count = collect_deps(dep, deps, current_count, depth + 1, max_count)

        i = i + 1
    end while

    return current_count
end collect_deps

// Create indentation string
fn make_indent(depth: int): string
    if depth == 0
        return ""
    end if

    mut result = ""
    mut i = 0
    while i < depth
        result = result + "  "
        i = i + 1
    end while
    return result
end make_indent

// Check if array contains a string
fn array_contains(arr: [string], count: int, s: string): bool
    mut i = 0
    while i < count
        if arr[i] == s
            return true
        end if
        i = i + 1
    end while
    return false
end array_contains

// Check if a dependency string represents alternatives (format: dep:opt1,opt2,opt3)
fn is_alternative_dep(dep: string): bool
    return str.contains(dep, ":")
end is_alternative_dep

// Parse alternative options from a dependency string
// Format: base_dep:alt1,alt2,alt3
// Returns number of alternatives parsed, fills alternatives array
fn parse_alternatives(dep: string, alternatives: [string], max_count: int): int
    let colon_pos = str.index_of_char(dep, ':')
    if colon_pos < 0
        // Not an alternative, return the single dependency
        alternatives[0] = dep
        return 1
    end if

    // Get the alternatives part after the colon
    let alts_part = str.substring(dep, colon_pos + 1, str.length(dep) - colon_pos - 1)

    // Split by comma
    return str.split(alts_part, ',', alternatives, max_count)
end parse_alternatives

// Get the base dependency name from an alternative string
fn get_base_dep(dep: string): string
    let colon_pos = str.index_of_char(dep, ':')
    if colon_pos < 0
        return dep
    end if
    return str.substring(dep, 0, colon_pos)
end get_base_dep

// Create empty AlternativeChoice
fn new_alternative_choice(): AlternativeChoice
    return AlternativeChoice{
        satisfied: false,
        provider: "",
        options: new [string](16),
        option_count: 0,
        base_dep: ""
    }
end new_alternative_choice

// Resolve an alternative dependency
// Returns satisfied=true if any option is already installed
// Otherwise returns the list of available options
fn resolve_alternative(dep: string): AlternativeChoice
    mut choice = new_alternative_choice()

    if not is_alternative_dep(dep)
        // Regular dependency
        choice.base_dep = dep
        choice.options[0] = dep
        choice.option_count = 1

        // Check if installed
        if database.is_installed(dep)
            choice.satisfied = true
            choice.provider = dep
        end if
        return choice
    end if

    // Parse the alternatives
    choice.base_dep = get_base_dep(dep)
    choice.option_count = parse_alternatives(dep, choice.options, 16)

    // Check if any alternative is already installed
    mut i = 0
    while i < choice.option_count
        let opt = choice.options[i]
        if database.is_installed(opt)
            choice.satisfied = true
            choice.provider = opt
            return choice
        end if
        i = i + 1
    end while

    // Check if any provides this via alternatives
    let provider = database.find_provider(choice.base_dep)
    if str.length(provider) > 0
        choice.satisfied = true
        choice.provider = provider
        return choice
    end if

    return choice
end resolve_alternative

// ============================================================================
// Build dependency resolver (resolves both runtime + build deps from source)
// ============================================================================

// Resolve all dependencies needed to build a package from source.
// Returns topological order: dependencies first, target package last.
// Resolves both runtime and build deps recursively.
// Uses proper cycle detection with separate visited/in_stack arrays.
fn resolve_build_deps(name: string): ResolveResult
    mut result = new_result()

    // Permanent marks: fully resolved packages
    mut visited: [string] = new [string](256)
    mut visited_count = 0

    // Temporary marks: packages on the current DFS stack (for cycle detection)
    mut in_stack: [string] = new [string](256)
    mut stack_count = 0

    // Topological build order
    mut order: [string] = new [string](256)
    mut order_count = 0

    let ok = resolve_build_recursive(name, visited, visited_count, in_stack, stack_count, order, order_count)

    if not ok.success
        result.error = ok.error
        return result
    end if

    result.success = true
    result.packages = ok.packages
    result.count = ok.count
    return result
end resolve_build_deps

fn resolve_build_recursive(name: string, visited: [string], visited_count: int,
                           in_stack: [string], stack_count: int,
                           order: [string], order_count: int): RecurseResult
    mut result = new_recurse_result()
    result.packages = order
    result.count = order_count

    // Permanent mark: already fully resolved, skip
    if array_contains(visited, visited_count, name)
        result.success = true
        return result
    end if

    // Temporary mark: cycle detected
    if array_contains(in_stack, stack_count, name)
        result.success = false
        result.error = "Circular dependency detected: " + name
        return result
    end if

    // If already installed, mark visited and skip (don't need to build)
    if database.is_installed(name)
        visited[visited_count] = name
        result.success = true
        return result
    end if

    // Find the port (must exist to build from source)
    let port_result = port.find(name)
    if not port_result.success
        // Check if a provider is already installed
        let provider = database.find_provider(name)
        if str.length(provider) > 0
            visited[visited_count] = name
            result.success = true
            return result
        end if

        result.success = false
        result.error = "Port not found: " + name
        return result
    end if

    let p = port_result.port
    let pkg_name = p.info.name

    // Push onto DFS stack (temporary mark)
    in_stack[stack_count] = name
    let new_stack_count = stack_count + 1

    // Mark as visited (permanent mark)
    visited[visited_count] = name
    let new_visited_count = visited_count + 1

    // Recurse into RUNTIME deps
    mut i = 0
    while i < p.deps.runtime_count
        let dep = p.deps.runtime[i]

        if is_alternative_dep(dep)
            let alt_choice = resolve_alternative(dep)
            if not alt_choice.satisfied and alt_choice.option_count > 0
                let chosen = alt_choice.options[0]
                let dep_result = resolve_build_recursive(chosen, visited, new_visited_count, in_stack, new_stack_count, result.packages, result.count)
                if not dep_result.success
                    return dep_result
                end if
                result.packages = dep_result.packages
                result.count = dep_result.count
            end if
        else
            let constraint = ver.parse_dep_constraint(dep)
            let dep_name = ver.constraint_name(constraint)

            mut needs_build = false
            if database.is_installed(dep_name)
                // Check version constraint
                if ver.has_constraint(constraint)
                    let installed_pkg = database.get_installed(dep_name)
                    if not ver.check_version_constraint(installed_pkg.info.version, ver.constraint_op(constraint), ver.constraint_version(constraint))
                        needs_build = true
                    end if
                end if
            else
                needs_build = true
            end if

            if needs_build
                let dep_result = resolve_build_recursive(dep_name, visited, new_visited_count, in_stack, new_stack_count, result.packages, result.count)
                if not dep_result.success
                    return dep_result
                end if
                result.packages = dep_result.packages
                result.count = dep_result.count
            end if
        end if

        i = i + 1
    end while

    // Recurse into BUILD deps
    i = 0
    while i < p.deps.build_count
        let dep = p.deps.build[i]

        if is_alternative_dep(dep)
            let alt_choice = resolve_alternative(dep)
            if not alt_choice.satisfied and alt_choice.option_count > 0
                let chosen = alt_choice.options[0]
                let dep_result = resolve_build_recursive(chosen, visited, new_visited_count, in_stack, new_stack_count, result.packages, result.count)
                if not dep_result.success
                    return dep_result
                end if
                result.packages = dep_result.packages
                result.count = dep_result.count
            end if
        else
            let constraint = ver.parse_dep_constraint(dep)
            let dep_name = ver.constraint_name(constraint)

            mut needs_build = false
            if database.is_installed(dep_name)
                if ver.has_constraint(constraint)
                    let installed_pkg = database.get_installed(dep_name)
                    if not ver.check_version_constraint(installed_pkg.info.version, ver.constraint_op(constraint), ver.constraint_version(constraint))
                        needs_build = true
                    end if
                end if
            else
                needs_build = true
            end if

            if needs_build
                let dep_result = resolve_build_recursive(dep_name, visited, new_visited_count, in_stack, new_stack_count, result.packages, result.count)
                if not dep_result.success
                    return dep_result
                end if
                result.packages = dep_result.packages
                result.count = dep_result.count
            end if
        end if

        i = i + 1
    end while

    // Post-order: add this package AFTER all its deps (topological sort)
    if not array_contains(result.packages, result.count, pkg_name)
        result.packages[result.count] = pkg_name
        result.count = result.count + 1
    end if

    result.success = true
    return result
end resolve_build_recursive

// ============================================================================
// Root-aware resolver functions for alternate root installation
// ============================================================================

// Internal result for rooted recursive resolution
type RootedRecurseResult = struct
    success: bool
    packages: [string]
    count: int
    error: string
end RootedRecurseResult

fn new_rooted_recurse_result(): RootedRecurseResult
    mut packages: [string] = new [string](256)
    return RootedRecurseResult{ success: true, packages: packages, count: 0, error: "" }
end new_rooted_recurse_result

// Resolve dependencies checking against a specific root
fn resolve_recursive_rooted(name: string, visited: [string], visited_count: int, order: [string], order_count: int, root: string): RootedRecurseResult
    mut result = new_rooted_recurse_result()
    result.packages = order
    result.count = order_count

    // Check for cycle
    if array_contains(visited, visited_count, name)
        result.success = true
        return result
    end if

    // Mark as visited
    visited[visited_count] = name
    let new_visited_count = visited_count + 1

    // Find the port
    let port_result = port.find(name)
    if not port_result.success
        // Check if already installed in target root
        if database.is_installed_rooted(name, root)
            result.success = true
            return result
        end if

        // Check if an alternative provider exists in target root
        // Note: find_provider doesn't have rooted version yet, skip for now
        result.success = false
        result.error = "Port not found: " + name
        return result
    end if

    let p = port_result.port
    let pkg_name = p.info.name

    // Resolve runtime dependencies first
    mut i = 0
    while i < p.deps.runtime_count
        let dep = p.deps.runtime[i]

        // Skip alternative deps for now (simplification)
        if not is_alternative_dep(dep)
            // Parse version constraint if present
            let constraint = ver.parse_dep_constraint(dep)
            let dep_name = ver.constraint_name(constraint)

            if database.is_installed_rooted(dep_name, root)
                // Check version constraint if present
                if ver.has_constraint(constraint)
                    let installed_pkg = database.get_installed_rooted(dep_name, root)
                    if not ver.check_version_constraint(installed_pkg.info.version, ver.constraint_op(constraint), ver.constraint_version(constraint))
                        // Needs upgrade
                        let dep_result = resolve_recursive_rooted(dep_name, visited, new_visited_count, result.packages, result.count, root)
                        if not dep_result.success
                            return dep_result
                        end if
                        result.packages = dep_result.packages
                        result.count = dep_result.count
                    end if
                end if
            else
                let dep_result = resolve_recursive_rooted(dep_name, visited, new_visited_count, result.packages, result.count, root)
                if not dep_result.success
                    return dep_result
                end if
                result.packages = dep_result.packages
                result.count = dep_result.count
            end if
        end if

        i = i + 1
    end while

    // Add this package to order (after its dependencies)
    // Use canonical name from package.toml, not the raw search argument
    if not array_contains(result.packages, result.count, pkg_name)
        // Skip if already installed in target root
        if not database.is_installed_rooted(pkg_name, root)
            result.packages[result.count] = pkg_name
            result.count = result.count + 1
        end if
    end if

    result.success = true
    return result
end resolve_recursive_rooted

// Resolve for a single package with root support
fn resolve_rooted(name: string, root: string): ResolveResult
    mut result = new_result()

    mut visited: [string] = new [string](256)
    mut visited_count = 0

    mut order: [string] = new [string](256)
    mut order_count = 0

    let ok = resolve_recursive_rooted(name, visited, visited_count, order, order_count, root)

    if not ok.success
        result.error = ok.error
        return result
    end if

    result.success = true
    result.packages = ok.packages
    result.count = ok.count
    return result
end resolve_rooted

// Get install order for multiple packages, checking against target root
fn get_install_order_rooted(names: [string], name_count: int, result: [string], max_count: int, root: string): int
    mut order_count = 0

    mut i = 0
    while i < name_count
        let name = names[i]
        let resolve_result = resolve_rooted(name, root)

        if resolve_result.success
            mut j = 0
            while j < resolve_result.count and order_count < max_count
                let pkg = resolve_result.packages[j]
                if not array_contains(result, order_count, pkg)
                    result[order_count] = pkg
                    order_count = order_count + 1
                end if
                j = j + 1
            end while
        end if

        i = i + 1
    end while

    return order_count
end get_install_order_rooted

end module