Валидация структур данных напротив схем

http://www.keks.cypherpunks.su/Schemas.html
С самого начала появления YAC/KEKS проекта я откладывал такую тему как
валидация структур данных. Сам по себе кодек должен быть schemaless: для
декодирования ничего дополнительного не нужно. Но схема всё же нужна для
задания какие поля, какого типа, какой длины, каких значений должны же
быть. Для JSON есть JSON Schema как пример.

Соответственно, нужно и понять как задавать схемы, а потом понять как их
применять и валидировать данные напротив них. JSON Schema или CDDL,
конечно, не вариант для Си -- слишком тяжеловесно. Генерировать код
декодирования или проверки из этих схем -- я не потяну такую задачу,
уверен что не простая, особенно когда, в отличии от ASN.1/protobuf,
порядок следования элементов не всегда априори известен.

Более чем полгода откладывал, но менее чем за неделю всё придумал и
реализовал. 90% всех проверок -- очень однообразны и просты. Можно
значит написать какие-то простые правила описывающие как проводить
проверки. Так сказать, сделать некую validation (virtual) machine,
которой управлять через подаваемые команды валидации. Предполагая, что
сама реализации такой верификации по командам/правилам/спецификациям
должна быть очень простой для реализации даже для Си.

В итоге реализовал подобное для Си и для Go. В Си это, если убрать
огромный код связанный с проверкой точности TAI полей и всякие
красивости поясняющие где и какая валидация не прошли -- это займёт
где-то 200-300 строк кода.

На вход нужно подавать команды валидации. Как их передать, как
закодировать? Конечно же использовать сам KEKS! В итоге имеем функцию
валидации, на вход которой подаются декодированные произвольные данные и
декодированные схемы. Каждая схема это просто последовательность команд
валидации.

Некоторые команды принимают n-ое кол-во аргументов, какие-то без них
вообще. Команды реализовал: ". k" -- "взять" элемент словаря или списка;
"E" -- проверить что взятый элементы существует; "!E" -- не существует;
"*" -- применить последующую команду для каждого элемента выбранного
словаря/списка; "T t0 [t1 ...]" -- проверить что тип выбранного элемента
находится в множестве (t0[, t1 ...]); "> n" -- проверить что значение
int или длина списка/словаря больше указанного числа; "< n" -- меньше;
"S s" -- проверить выбранный элемент напротив схемы s; "TMP p" -- time
maximal precision, проверить что точность выбранного поля со временем не
превышает указанную; "= v" -- проверить что выбранная строка равна v.

Например проверка такой CDDL схемы:

    ai = text .gt 0
    fpr = bytes .size 32
    our = {a: ai, v: bytes/text, fpr: fpr, ?comment: text}

будет выражаться таким набором команд:

    {"our": [
        [".", "a"],
        ["E"],
        [".", "a"],
        ["T", "STR"],
        [".", "a"],
        [">", 0],

        [".", "v"],
        ["E"],
        [".", "v"],
        ["T", "BIN", "STR"],

        [".", "fpr"],
        ["E"],
        [".", "fpr"],
        ["T", "BIN"],
        [".", "fpr"],
        [">", 31],
        [".", "fpr"],
        ["<", 33],

        [".", "comment"],
        ["T", "STR"],
    ]}

    latitude = -90..90
    longitude = -180..180
    where = [latitude, longitude]
    wheres = [+ where]

    {
        "where": [
            [".", "."],
            ["T", "LIST"],
            [".", "."],
            [">", 1],
            [".", "."],
            ["<", 3],
            [".", "."],
            ["*"],
            [".", "INT"],
            [".", 0],
            [">", -91],
            [".", 0],
            ["<", 91],
            [".", 1],
            [">", -181],
            [".", 1],
            ["<", 181],
        ],
        "wheres": [
            [".", "."],
            ["T", "LIST"],
            [".", "."],
            [">", 0],
            [".", "."],
            ["*"],
            ["S", "where"],
        ],
    }

По сути это такой встроенный интерпретатор. Но достаточный для 90%+ всех
задач связанных с проверкой напротив схем. А если чего сильно будет не
хватать, то можно и новые команды добавить.

Как их генерировать? Я написал реализацию на Tcl, в которой множество
вспомогательных коммандочек имеется. В итоге содержимое файла с полным
описанием правил валидации публичного ключа (который может быть
подписан, который является и cm/signed структурой):
    SCHEMAS {
        av {
            {HAS a}
            {TYPE= a {STR}}
            {!EMPTY a}
            {HAS v}
            {TYPE= v {BIN}}
        }

        pub {
            {HAS load}
            {SCHEMA= load load}
            {TYPE= sigs {LIST}}
            {SCHEMA* sigs sig}

            {TYPE= pubs {LIST}}
            {!EMPTY pubs}
            {SCHEMA* pubs pub}
        }

        load {
            {HAS t}
            {STR= t pub}
            {HAS v}
            {SCHEMA= v pub-load}
        }

        sig {
            {HAS tbs}
            {HAS sign}
            {SCHEMA= tbs tbs}
            {SCHEMA= sign av}
        }

        exp {
            {TYPE= . {LIST}}
            {LEN= . 2}
            {TYPE* . {TAI64}}
            {TAKE .}
            {EACH}
            {TIMEMAXPREC 0}
        }

        fpr {
            {TYPE= . {BIN}}
            {LEN= . 32}
        }

        tbs {
            {HAS sid}
            {SCHEMA= sid fpr}

            {HAS cid}
            {TYPE= cid {HEXLET}}

            {HAS exp}
            {SCHEMA= exp exp}

            {TYPE= nonce {BIN}}
            {!EMPTY nonce}

            {TYPE= when {TAI64}}
        }

        pub-load {
            {HAS id}
            {SCHEMA= id fpr}

            {!HAS crit}

            {IS-SET ku}

            {HAS pub}
            {TYPE= pub {LIST}}
            {!EMPTY pub}
            {SCHEMA* pub av}

            {HAS sub}
            {TYPE= sub {MAP}}
            {!EMPTY sub}
            {TYPE* sub {STR}}
        }
    }

Что, с моей точки зрения, не сильно и не существенно отличается от
описаний ASN.1 или CDDL. Я их писал просто с ходу, без запинок, без
особых раздумий. В самой Tcl утилитке, например STR= (убедиться что k
является строкой со значением v) описан вот так:

    proc STR= {k v} {
        evals [subst {
            {TAKE $k}
            {TYPE {STR}}
            {TAKE $k}
            {EQ $v}
        }]
    }

где более низкоуровневые TAKE, TAKE, EQ команды описаны так:

    proc TAKE {v} {
        if {[string is digit $v]} {set v [list INT $v]} {set v [list STR $v]}
        subst {{LIST {{STR .} {$v}}}}
    }
    proc EQ {v} {subst {{LIST {{STR =} {STR $v}}}}}
    proc TYPE {vs} {
        set l {{STR T}}
        foreach v $vs {lappend l "STR $v"}
        subst {{LIST {$l}}}
    }

а какой-нибудь IS-SET:

    proc IS-SET {k} {
        evals [subst {
            {TAKE $k}
            {TYPE {MAP}}
            {TAKE $k}
            {GT 0}
            {TAKE $k}
            {EACH}
            {TYPE {NIL}}
        }]
    }

что затем уже через LIST/STR/INT команды кодируется в KEKS.
Соответственно, пишем на Tcl подобные схемы, преобразуем их в KEKS
файлы, через go:embed встраиваем во время компиляции в Go код, где
декодируем и передаём в функции валидации. Аналогично и для Си. А так
как схемы, в общем то, являются самыми обычными Tcl программами, то там
всякого можно понапридумывать для сокращения писанины.

По моему вышло здорово. Пока функции валидации ещё не покрыты тестами,
но это явно не сложная задача, ибо команд не много. Зато теперь можно
настоящие схемы писать, а не то что я на сайте показываю, чисто для
человеков. И свои Go утилитки у меня уже используют это всё для
валидации файлов с ключами, подписанных и зашифрованных контейнеров.

Я тут далёк от всей темы, но не Тьюринг-ли полный у меня язык вышел?
А то наслышан, что нечаянно сделать подобное -- относительно легко. Но
это не должно быть проблемой, ибо не предполагается что схемы из
недоверенных источников могут приходить.