// Strict drivers.ini v2 parsing, validation and dependency evaluation.

#include <kernel/dm_config.h>
#include <string.h>

#define DM_DRIVER_IMAGE_SET 1u
#define DM_DRIVER_START_SET 2u
#define DM_DRIVER_CLASS_SET 4u
#define DM_DRIVER_CRITICAL_SET 8u
#define DM_DRIVER_REQUIRES_SET 16u
#define DM_DRIVER_AFTER_SET 32u
#define DM_CLASS_REQUIRES_SET 1u
#define DM_CLASS_AFTER_SET 2u

static bool DmFail(char* error, size_t capacity, const char* message) {
    if (error && capacity) {
        size_t i = 0;
        while (message[i] && i + 1 < capacity) {
            error[i] = message[i];
            ++i;
        }
        error[i] = '\0';
    }
    return false;
}

static bool DmSpace(char c) {
    return c == ' ' || c == '\t' || c == '\r';
}

static void DmTrim(const char** begin, const char** end) {
    while (*begin < *end && DmSpace(**begin)) ++*begin;
    while (*end > *begin && DmSpace((*end)[-1])) --*end;
}

static bool DmEqual(const char* begin, const char* end, const char* value) {
    while (begin < end && *value && *begin == *value) {
        ++begin;
        ++value;
    }
    return begin == end && !*value;
}

static bool DmIdentifier(const char* begin, const char* end) {
    if (begin == end || (size_t)(end - begin) >= DM_ID_MAX) return false;
    for (const char* p = begin; p < end; ++p) {
        char c = *p;
        if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
              (c >= '0' && c <= '9') || c == '.' || c == '-' || c == '_')) return false;
    }
    return true;
}

// PE import module names are compared without ASCII case distinctions.
static bool DmImageEqual(const char* a, const char* b) {
    while (*a && *b) {
        char x = *a++;
        char y = *b++;
        if (x >= 'A' && x <= 'Z') x = (char)(x + ('a' - 'A'));
        if (y >= 'A' && y <= 'Z') y = (char)(y + ('a' - 'A'));
        if (x != y) return false;
    }
    return !*a && !*b;
}

static bool DmCopy(char* out, size_t capacity, const char* begin, const char* end) {
    size_t size = (size_t)(end - begin);
    if (!size || size >= capacity) return false;
    memcpy(out, begin, size);
    out[size] = '\0';
    return true;
}

static int DmFindDriver(const DM_CONFIG* config, const char* id) {
    for (uint32_t i = 0; i < config->DriverCount; ++i)
        if (!strcmp(config->Drivers[i].Id, id)) return (int)i;
    return -1;
}

static int DmFindClass(const DM_CONFIG* config, const char* id) {
    for (uint32_t i = 0; i < config->ClassCount; ++i)
        if (!strcmp(config->Classes[i].Id, id)) return (int)i;
    return -1;
}

static bool DmParseEdges(DM_EDGES* edges, const char* begin, const char* end,
                         DM_DEPENDENCY_KIND kind) {
    if (begin == end) return true;
    while (begin < end) {
        const char* finish = begin;
        while (finish < end && *finish != ',') ++finish;
        const char* tokenEnd = finish;
        DmTrim(&begin, &tokenEnd);
        if (!DmIdentifier(begin, tokenEnd) || edges->Count == DM_MAX_EDGES) return false;
        for (uint32_t i = 0; i < edges->Count; ++i) {
            if (edges->Items[i].Kind == kind &&
                DmEqual(begin, tokenEnd, edges->Items[i].Id)) return false;
        }
        DM_DEPENDENCY* edge = &edges->Items[edges->Count++];
        edge->Kind = kind;
        if (!DmCopy(edge->Id, sizeof(edge->Id), begin, tokenEnd)) return false;
        if (finish == end) return true;
        begin = finish + 1;
        DmTrim(&begin, &end);
        if (begin == end) return false;
    }
    return true;
}

// Validates references and boot-phase satisfiability without flattening class alternatives.
static bool DmValidateEdges(const DM_CONFIG* config, const DM_EDGES* edges,
                            const DM_DRIVER_CONFIG* source, bool required) {
    for (uint32_t i = 0; i < edges->Count; ++i) {
        const DM_DEPENDENCY* edge = &edges->Items[i];
        if (edge->Kind == DmDependencyDriver) {
            int target = DmFindDriver(config, edge->Id);
            if (target < 0) return false;
            if (source && source->Phase == DmStartBoot &&
                config->Drivers[target].Phase != DmStartBoot) return false;
        } else {
            if (DmFindClass(config, edge->Id) < 0) return false;
            uint32_t bootProviders = 0;
            for (uint32_t j = 0; j < config->DriverCount; ++j) {
                if (strcmp(config->Drivers[j].Class, edge->Id)) continue;
                if (config->Drivers[j].Phase == DmStartBoot) ++bootProviders;
            }
            if (required && source && source->Phase == DmStartBoot && !bootProviders)
                return false;
        }
    }
    return true;
}

static bool DmEdgesOverlap(const DM_EDGES* requires, const DM_EDGES* after) {
    for (uint32_t i = 0; i < requires->Count; ++i)
        for (uint32_t j = 0; j < after->Count; ++j)
            if (requires->Items[i].Kind == after->Items[j].Kind &&
                !strcmp(requires->Items[i].Id, after->Items[j].Id)) return true;
    return false;
}

static bool DmVisitClass(uint32_t index, uint32_t count,
                         uint8_t color[DM_MAX_CLASSES],
                         uint8_t graph[DM_MAX_CLASSES][DM_MAX_CLASSES]) {
    color[index] = 1;
    for (uint32_t j = 0; j < count; ++j) {
        if (!graph[index][j]) continue;
        if (color[j] == 1 ||
            (color[j] == 0 && !DmVisitClass(j, count, color, graph))) return false;
    }
    color[index] = 2;
    return true;
}

bool DmConfigParse(DM_CONFIG* config, const char* bytes, size_t size,
                   char* error, size_t errorCapacity) {
    if (!config || !bytes || size == 0 || size > DM_CONFIG_MAX_BYTES)
        return DmFail(error, errorCapacity, "invalid configuration size");
    memset(config, 0, sizeof(*config));
    DM_DRIVER_CONFIG* driver = NULL;
    DM_CLASS_CONFIG* cls = NULL;
    bool seenDriverSection = false;
    size_t pos = 0;
    while (pos < size) {
        size_t line = pos;
        while (pos < size && bytes[pos] != '\n') ++pos;
        const char* begin = bytes + line;
        const char* end = bytes + pos;
        if (pos < size) ++pos;
        DmTrim(&begin, &end);
        if (begin == end || *begin == ';' || *begin == '#') continue;
        if (*begin == '[') {
            if (end[-1] != ']' || (size_t)(end - begin) < 4)
                return DmFail(error, errorCapacity, "invalid section");
            const char* name = begin + 1;
            const char* nameEnd = end - 1;
            driver = NULL;
            cls = NULL;
            if ((size_t)(nameEnd - name) > 7 && !memcmp(name, "driver.", 7)) {
                name += 7;
                if (!DmIdentifier(name, nameEnd) || config->DriverCount == DM_MAX_DRIVERS)
                    return DmFail(error, errorCapacity, "invalid driver id or driver limit");
                driver = &config->Drivers[config->DriverCount++];
                seenDriverSection = true;
                if (!DmCopy(driver->Id, sizeof(driver->Id), name, nameEnd)) return false;
                for (uint32_t i = 0; i + 1 < config->DriverCount; ++i)
                    if (!strcmp(config->Drivers[i].Id, driver->Id))
                        return DmFail(error, errorCapacity, "duplicate driver id");
            } else if ((size_t)(nameEnd - name) > 6 && !memcmp(name, "class.", 6)) {
                name += 6;
                if (!DmIdentifier(name, nameEnd) || config->ClassCount == DM_MAX_CLASSES)
                    return DmFail(error, errorCapacity, "invalid class id or class limit");
                if (seenDriverSection)
                    return DmFail(error, errorCapacity, "class declared after driver");
                cls = &config->Classes[config->ClassCount++];
                if (!DmCopy(cls->Id, sizeof(cls->Id), name, nameEnd)) return false;
                for (uint32_t i = 0; i + 1 < config->ClassCount; ++i)
                    if (!strcmp(config->Classes[i].Id, cls->Id))
                        return DmFail(error, errorCapacity, "duplicate class id");
            } else return DmFail(error, errorCapacity, "unknown section");
            continue;
        }
        if (!driver && !cls) return DmFail(error, errorCapacity, "key outside section");
        const char* equal = begin;
        while (equal < end && *equal != '=') ++equal;
        if (equal == end) return DmFail(error, errorCapacity, "missing equals");
        const char* keyEnd = equal;
        const char* value = equal + 1;
        DmTrim(&begin, &keyEnd);
        DmTrim(&value, &end);
        for (const char* p = value; p < end; ++p) {
            if (*p == ';' || *p == '#') {
                end = p;
                DmTrim(&value, &end);
                break;
            }
        }
        uint8_t mask = 0;
        if (driver) {
            if (DmEqual(begin, keyEnd, "image")) {
                mask = DM_DRIVER_IMAGE_SET;
                if (!DmCopy(driver->Image, sizeof(driver->Image), value, end))
                    return DmFail(error, errorCapacity, "invalid image");
                for (const char* p = value; p < end; ++p)
                    if (!((*p >= 'a' && *p <= 'z') || (*p >= 'A' && *p <= 'Z') ||
                          (*p >= '0' && *p <= '9') ||
                          *p == '-' || *p == '_' || *p == '.'))
                        return DmFail(error, errorCapacity, "invalid image filename");
                if (end - value < 5 || memcmp(end - 4, ".sys", 4))
                    return DmFail(error, errorCapacity, "image must be a .sys file");
            } else if (DmEqual(begin, keyEnd, "start")) {
                mask = DM_DRIVER_START_SET;
                if (DmEqual(value, end, "boot")) driver->Phase = DmStartBoot;
                else if (DmEqual(value, end, "runtime")) driver->Phase = DmStartRuntime;
                else if (DmEqual(value, end, "disabled")) {
                    driver->Phase = DmStartDisabled;
                    driver->State = DmRunDisabled;
                }
                else return DmFail(error, errorCapacity, "invalid start phase");
            } else if (DmEqual(begin, keyEnd, "class")) {
                mask = DM_DRIVER_CLASS_SET;
                if (value != end && (!DmIdentifier(value, end) ||
                    !DmCopy(driver->Class, sizeof(driver->Class), value, end)))
                    return DmFail(error, errorCapacity, "invalid class");
            } else if (DmEqual(begin, keyEnd, "requires")) {
                mask = DM_DRIVER_REQUIRES_SET;
                if (!DmParseEdges(&driver->Requires, value, end, DmDependencyDriver))
                    return DmFail(error, errorCapacity, "invalid requires");
            } else if (DmEqual(begin, keyEnd, "after")) {
                mask = DM_DRIVER_AFTER_SET;
                if (!DmParseEdges(&driver->After, value, end, DmDependencyDriver))
                    return DmFail(error, errorCapacity, "invalid after");
            } else if (DmEqual(begin, keyEnd, "critical")) {
                mask = DM_DRIVER_CRITICAL_SET;
                if (value == end) driver->Critical = false;
                else if (DmEqual(value, end, "true")) driver->Critical = true;
                else if (DmEqual(value, end, "false")) driver->Critical = false;
                else return DmFail(error, errorCapacity, "invalid critical value");
            } else return DmFail(error, errorCapacity, "unknown driver key");
            if (driver->Present & mask) return DmFail(error, errorCapacity, "duplicate driver key");
            driver->Present |= mask;
        } else {
            if (DmEqual(begin, keyEnd, "requires")) {
                mask = DM_CLASS_REQUIRES_SET;
                if (!DmParseEdges(&cls->Requires, value, end, DmDependencyClass))
                    return DmFail(error, errorCapacity, "invalid class requires");
            } else if (DmEqual(begin, keyEnd, "after")) {
                mask = DM_CLASS_AFTER_SET;
                if (!DmParseEdges(&cls->After, value, end, DmDependencyClass))
                    return DmFail(error, errorCapacity, "invalid class after");
            } else return DmFail(error, errorCapacity, "unknown class key");
            if (cls->Present & mask) return DmFail(error, errorCapacity, "duplicate class key");
            cls->Present |= mask;
        }
    }
    if (!config->DriverCount) return DmFail(error, errorCapacity, "no drivers");
    // Class graph is checked independently even when a class has no providers.
    uint8_t classGraph[DM_MAX_CLASSES][DM_MAX_CLASSES] = {{0}};
    for (uint32_t i = 0; i < config->ClassCount; ++i) {
        const DM_CLASS_CONFIG* cls = &config->Classes[i];
        if (DmEdgesOverlap(&cls->Requires, &cls->After))
            return DmFail(error, errorCapacity, "conflicting class dependency");
        const DM_EDGES* lists[] = { &cls->Requires, &cls->After };
        for (uint32_t k = 0; k < 2; ++k)
            for (uint32_t j = 0; j < lists[k]->Count; ++j) {
                int index = DmFindClass(config, lists[k]->Items[j].Id);
                if (index < 0) return DmFail(error, errorCapacity, "unknown class dependency");
                classGraph[i][index] = 1;
            }
    }
    uint8_t classColors[DM_MAX_CLASSES] = {0};
    for (uint32_t i = 0; i < config->ClassCount; ++i)
        if (!classColors[i] && !DmVisitClass(i, config->ClassCount,
                                             classColors, classGraph))
            return DmFail(error, errorCapacity, "class dependency cycle");
    for (uint32_t i = 0; i < config->DriverCount; ++i) {
        DM_DRIVER_CONFIG* d = &config->Drivers[i];
        if ((d->Present & (DM_DRIVER_IMAGE_SET | DM_DRIVER_START_SET)) !=
            (DM_DRIVER_IMAGE_SET | DM_DRIVER_START_SET))
            return DmFail(error, errorCapacity, "driver needs image and start");
        for (uint32_t j = 0; j < i; ++j)
            if (d->Phase != DmStartDisabled &&
                config->Drivers[j].Phase != DmStartDisabled &&
                DmImageEqual(config->Drivers[j].Image, d->Image))
                return DmFail(error, errorCapacity, "duplicate image");
        if (d->Class[0] && DmFindClass(config, d->Class) < 0)
            return DmFail(error, errorCapacity, "undeclared driver class");
        if (DmEdgesOverlap(&d->Requires, &d->After))
            return DmFail(error, errorCapacity, "conflicting driver dependency");
        if (!DmValidateEdges(config, &d->Requires, d, true) ||
            !DmValidateEdges(config, &d->After, d, false))
            return DmFail(error, errorCapacity, "invalid driver dependency or phase");
        if (d->Class[0] && d->Phase != DmStartDisabled) {
            DM_CLASS_CONFIG* c = &config->Classes[DmFindClass(config, d->Class)];
            if (!DmValidateEdges(config, &c->Requires, d, true) ||
                !DmValidateEdges(config, &c->After, d, false))
                return DmFail(error, errorCapacity, "invalid class dependency or phase");
        }
    }
    // An optimistic dry run models requires= as an OR over class providers and
    // after= as a settlement barrier. It detects real combined deadlocks without
    // rejecting a class merely because one alternative provider depends on it.
    for (uint32_t phase = DmStartBoot; phase <= DmStartRuntime; ++phase) {
        config->ActivePhase = (DM_START_PHASE)phase;
        for (;;) {
            bool progress = false;
            for (uint32_t i = 0; i < config->DriverCount; ++i) {
                DM_DRIVER_CONFIG* d = &config->Drivers[i];
                if (d->Phase != phase || d->State != DmRunWaiting) continue;
                if (DmDriverCanStart(config, i)) {
                    d->State = DmRunStarted;
                    progress = true;
                } else if (DmDriverIsBlocked(config, i)) {
                    d->State = DmRunBlocked;
                    progress = true;
                }
            }
            if (!progress) break;
        }
        for (uint32_t i = 0; i < config->DriverCount; ++i)
            if (config->Drivers[i].Phase == phase &&
                config->Drivers[i].State == DmRunWaiting)
                return DmFail(error, errorCapacity, "unschedulable dependency cycle");
    }
    for (uint32_t i = 0; i < config->DriverCount; ++i)
        if (config->Drivers[i].Phase != DmStartDisabled)
            config->Drivers[i].State = DmRunWaiting;
    config->ActivePhase = DmStartBoot;
    return true;
}

bool DmClassSettled(const DM_CONFIG* config, const char* classId) {
    for (uint32_t i = 0; i < config->DriverCount; ++i) {
        const DM_DRIVER_CONFIG* driver = &config->Drivers[i];
        if (!strcmp(driver->Class, classId) &&
            (config->ActivePhase == DmStartRuntime || driver->Phase == DmStartBoot) &&
            driver->State == DmRunWaiting) return false;
    }
    return true;
}

bool DmClassAvailable(const DM_CONFIG* config, const char* classId) {
    for (uint32_t i = 0; i < config->DriverCount; ++i) {
        const DM_DRIVER_CONFIG* driver = &config->Drivers[i];
        if (!strcmp(driver->Class, classId) && driver->State == DmRunStarted) return true;
    }
    return false;
}

static bool DmEdgesReady(const DM_CONFIG* config, const DM_EDGES* edges, bool required) {
    for (uint32_t i = 0; i < edges->Count; ++i) {
        const DM_DEPENDENCY* edge = &edges->Items[i];
        if (edge->Kind == DmDependencyClass) {
            if (required ? !DmClassAvailable(config, edge->Id) :
                           !DmClassSettled(config, edge->Id)) return false;
        } else {
            int index = DmFindDriver(config, edge->Id);
            if (index < 0) return false;
            DM_RUN_STATE state = config->Drivers[index].State;
            if (required ? state != DmRunStarted : state == DmRunWaiting) return false;
        }
    }
    return true;
}

bool DmDriverCanStart(const DM_CONFIG* config, uint32_t index) {
    if (!config || index >= config->DriverCount) return false;
    const DM_DRIVER_CONFIG* driver = &config->Drivers[index];
    if (driver->State != DmRunWaiting ||
        !DmEdgesReady(config, &driver->Requires, true) ||
        !DmEdgesReady(config, &driver->After, false)) return false;
    if (!driver->Class[0]) return true;
    const DM_CLASS_CONFIG* cls = &config->Classes[DmFindClass(config, driver->Class)];
    return DmEdgesReady(config, &cls->Requires, true) &&
           DmEdgesReady(config, &cls->After, false);
}

static bool DmEdgesImpossible(const DM_CONFIG* config, const DM_EDGES* edges) {
    for (uint32_t i = 0; i < edges->Count; ++i) {
        const DM_DEPENDENCY* edge = &edges->Items[i];
        if (edge->Kind == DmDependencyClass) {
            if (DmClassSettled(config, edge->Id) &&
                !DmClassAvailable(config, edge->Id)) return true;
        } else {
            int index = DmFindDriver(config, edge->Id);
            if (index < 0 || config->Drivers[index].State == DmRunFailed ||
                config->Drivers[index].State == DmRunBlocked ||
                config->Drivers[index].State == DmRunDisabled) return true;
        }
    }
    return false;
}

bool DmDriverIsBlocked(const DM_CONFIG* config, uint32_t index) {
    if (!config || index >= config->DriverCount) return false;
    const DM_DRIVER_CONFIG* driver = &config->Drivers[index];
    if (driver->State != DmRunWaiting) return false;
    if (DmEdgesImpossible(config, &driver->Requires)) return true;
    if (!driver->Class[0]) return false;
    return DmEdgesImpossible(config,
        &config->Classes[DmFindClass(config, driver->Class)].Requires);
}