mirror of
https://github.com/revng/revng
synced 2026-06-21 14:07:57 +00:00
Ivan Krysak
cc57e57fd1
After this commit, every non-key field is treated as if it was optional while every key field (plus every auto-generated `Kind` field) - as if it was required.
618 lines
18 KiB
TypeScript
618 lines
18 KiB
TypeScript
/**
|
|
* This file is distributed under the MIT License. See LICENSE.md for details.
|
|
*/
|
|
|
|
import * as yaml from "yaml";
|
|
|
|
export const yamlParseOptions = {
|
|
strict: false,
|
|
logLevel: "silent",
|
|
intAsBigInt: true,
|
|
} as const;
|
|
|
|
export const yamlOutParseOptions = {
|
|
keepUndefined: false,
|
|
} as const;
|
|
|
|
export const yamlToStringOptions = {
|
|
doubleQuotedAsJSON: false,
|
|
defaultKeyType: yaml.Scalar.PLAIN,
|
|
defaultStringType: yaml.Scalar.QUOTE_DOUBLE,
|
|
directives: true,
|
|
lineWidth: 0,
|
|
} as const;
|
|
|
|
export type IReference = string;
|
|
|
|
/**
|
|
* Reference class
|
|
* Represents a pointer to another element of the Tuple Tree, which can be fetched via 'resolve'
|
|
*/
|
|
export class Reference<T, M> {
|
|
reference: string;
|
|
|
|
constructor(ref: string) {
|
|
this.reference = ref;
|
|
}
|
|
|
|
toJSON(): string {
|
|
return this.reference;
|
|
}
|
|
|
|
toString(): string {
|
|
return this.reference;
|
|
}
|
|
|
|
equals(other: unknown): boolean {
|
|
if (other instanceof Reference<T, M>) {
|
|
return this.reference == other.reference;
|
|
} else {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
resolve(root: M): T | undefined {
|
|
return _getElementByPath<T>(this.reference, root);
|
|
}
|
|
|
|
isValid(): boolean {
|
|
return this.reference !== "";
|
|
}
|
|
|
|
static parse<T, M>(ref?: string): Reference<T, M> {
|
|
return new Reference(ref || "");
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Generate a random hexadecimal string
|
|
* @param length output string length
|
|
* @returns a random string
|
|
*/
|
|
function randomBytes(length: number): string {
|
|
let value = "";
|
|
for (let i = 0; i < length; i++) {
|
|
value += (Math.random() * 16).toString(16);
|
|
}
|
|
return value;
|
|
}
|
|
|
|
/**
|
|
* Generate a random bigint, between [start, end)
|
|
* @param start lower bound
|
|
* @param end upper bound
|
|
* @returns random bigint
|
|
*/
|
|
function randomBigint(start: bigint, end: bigint): bigint {
|
|
const diff = end - start;
|
|
let value = end;
|
|
do {
|
|
const randomLength = diff.toString().length * Math.random();
|
|
value = BigInt(`0x${randomBytes(randomLength)}`);
|
|
} while (value > diff);
|
|
return value + start;
|
|
}
|
|
|
|
/**
|
|
* Utility function that returns a bigint suitable for IDs
|
|
* @returns guid ID
|
|
*/
|
|
export function genGuid(): bigint {
|
|
return randomBigint(2n ** 10n + 1n, 2n ** 64n - 1n);
|
|
}
|
|
|
|
// Tree traversal
|
|
|
|
function getElementByPathArray<T>(path: string[], obj: any): T | undefined {
|
|
if (obj === undefined) {
|
|
return undefined;
|
|
}
|
|
|
|
let component = path[0];
|
|
if (obj instanceof Array) {
|
|
for (const elem of obj) {
|
|
if (keyableObject(elem) && elem.key() == component) {
|
|
if (path.length == 1) {
|
|
return elem as unknown as T;
|
|
} else {
|
|
return getElementByPathArray(path.slice(1), elem);
|
|
}
|
|
}
|
|
}
|
|
return undefined;
|
|
} else {
|
|
if (component.includes("::")) {
|
|
const parts = component.split("::", 2);
|
|
component = parts[1];
|
|
if (obj.Kind !== parts[0]) {
|
|
return undefined;
|
|
}
|
|
}
|
|
if (component in obj) {
|
|
if (path.length == 1) {
|
|
return obj[component];
|
|
} else {
|
|
return getElementByPathArray(path.slice(1), obj[component]);
|
|
}
|
|
} else {
|
|
return undefined;
|
|
}
|
|
}
|
|
}
|
|
|
|
function setElementByPathArray<T>(path: string[], obj: any, value: T): boolean {
|
|
if (obj === undefined) {
|
|
return false;
|
|
}
|
|
|
|
let component = path[0];
|
|
if (obj instanceof Array) {
|
|
const index = obj.findIndex((elem) => keyableObject(elem) && elem.key() === component);
|
|
|
|
if (index >= 0) {
|
|
if (path.length === 1) {
|
|
obj[index] = value;
|
|
return true;
|
|
} else {
|
|
return setElementByPathArray(path.slice(1), obj[index], value);
|
|
}
|
|
} else if (
|
|
index === -1 &&
|
|
path.length === 1 &&
|
|
keyableObject(value) &&
|
|
value.key() === component
|
|
) {
|
|
// We're appending a value to an array
|
|
obj.push(value);
|
|
return true;
|
|
} else {
|
|
return false;
|
|
}
|
|
} else {
|
|
if (component.includes("::")) {
|
|
const parts = component.split("::", 2);
|
|
component = parts[1];
|
|
if (obj.Kind !== parts[0]) {
|
|
return false;
|
|
}
|
|
}
|
|
if (component in obj) {
|
|
if (path.length == 1) {
|
|
obj[component] = value;
|
|
return true;
|
|
} else {
|
|
return setElementByPathArray(path.slice(1), obj[component], value);
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Given a Tuple Tree path and a root object, resolve the object or return
|
|
* undefined if the path is not present in the tuple tree
|
|
*/
|
|
export function _getElementByPath<T>(path: string, obj: any): T | undefined {
|
|
return getElementByPathArray(path.split("/").slice(1), obj);
|
|
}
|
|
|
|
/**
|
|
* Given a Tuple Tree path, a root object and a value, set the path with the
|
|
* value provided and return true. If the path does not resolve, this returns
|
|
* false
|
|
*/
|
|
export function _setElementByPath<T>(path: string, obj: any, value: T): boolean {
|
|
return setElementByPathArray(path.split("/").slice(1), obj, value);
|
|
}
|
|
|
|
// Tree Diffing
|
|
|
|
interface IDiffSet {
|
|
Changes: IDiff[];
|
|
}
|
|
|
|
export class DiffSet {
|
|
Changes: Diff[];
|
|
|
|
constructor(Changes: Diff[]) {
|
|
this.Changes = Changes;
|
|
}
|
|
|
|
static parse(rawObject: IDiffSet): DiffSet {
|
|
return new DiffSet(rawObject.Changes.map((e) => new Diff(e.Path, e.Add, e.Remove)));
|
|
}
|
|
|
|
toJSON(): IDiffSet {
|
|
return {
|
|
Changes: this.Changes.filter((e) => e.isValid()).map((e) => e.toJSON()),
|
|
};
|
|
}
|
|
|
|
reversed(): DiffSet {
|
|
return new DiffSet(this.Changes.map((e) => new Diff(e.Path, e.Remove, e.Add)));
|
|
}
|
|
|
|
static deserialize(input: string): DiffSet {
|
|
return DiffSet.parse(yaml.parse(input));
|
|
}
|
|
|
|
serialize(): string {
|
|
const doc = new yaml.Document(this, yamlOutParseOptions);
|
|
return doc.toString(yamlToStringOptions);
|
|
}
|
|
}
|
|
|
|
interface IDiff {
|
|
Path: string;
|
|
Add?: any;
|
|
Remove?: any;
|
|
}
|
|
|
|
class Diff {
|
|
Path: string;
|
|
Add: any;
|
|
Remove: any;
|
|
|
|
constructor(Path: string, Add: any, Remove: any) {
|
|
this.Path = Path;
|
|
this.Add = Add;
|
|
this.Remove = Remove;
|
|
}
|
|
|
|
toJSON(): IDiff {
|
|
let ret = { Path: this.Path };
|
|
if (this.Add !== undefined) {
|
|
ret["Add"] = this.Add;
|
|
}
|
|
if (this.Remove !== undefined) {
|
|
ret["Remove"] = this.Remove;
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
isValid(): boolean {
|
|
return this.Add !== undefined || this.Remove !== undefined;
|
|
}
|
|
}
|
|
|
|
function isNull(obj: any): obj is undefined | null {
|
|
return obj === undefined || obj === null;
|
|
}
|
|
|
|
function hasEquals(obj: any): obj is { equals: (other: unknown) => boolean } {
|
|
return typeof obj === "object" && typeof obj?.equals === "function";
|
|
}
|
|
|
|
function keyableObject(obj: any): obj is { key: () => string } {
|
|
return (
|
|
obj !== null &&
|
|
typeof obj === "object" &&
|
|
"key" in obj &&
|
|
typeof obj.key === "function" &&
|
|
typeof obj.key() === "string"
|
|
);
|
|
}
|
|
|
|
export function _makeDiff<T>(
|
|
tuple_tree_old: T,
|
|
tuple_tree_new: T,
|
|
typesMetadata: TypesMetadata,
|
|
rootType: Constructor
|
|
): DiffSet {
|
|
const rootTypeInfo: ConstructorType = {
|
|
type: rootType,
|
|
ctor: "class",
|
|
isArray: false,
|
|
isAbstract: false,
|
|
};
|
|
return new DiffSet(
|
|
makeDiffSubtree(tuple_tree_old, tuple_tree_new, "", typesMetadata, rootTypeInfo, false)
|
|
);
|
|
}
|
|
|
|
export function makeDiffSubtree(
|
|
obj_old: any,
|
|
obj_new: any,
|
|
prefix: string,
|
|
typesMetadata: TypesMetadata,
|
|
typeInfo: TypeInfo,
|
|
inArray: boolean
|
|
): Diff[] {
|
|
const result: Diff[] = [];
|
|
if (typeof obj_old != typeof obj_new) {
|
|
return [];
|
|
}
|
|
|
|
let infoObject: TypeInfoObject;
|
|
let upcast = false;
|
|
if (typeInfo.isAbstract) {
|
|
const derivedClass = (
|
|
typeInfo.type as unknown as { parseClass: (obj) => Constructor | undefined }
|
|
).parseClass(obj_old);
|
|
const baseInfoObject = typesMetadata.get(typeInfo.type as Constructor | Parsable);
|
|
if (derivedClass !== undefined) {
|
|
const derivedClassObject = typesMetadata.get(derivedClass);
|
|
infoObject = { ...baseInfoObject, ...derivedClassObject };
|
|
upcast = true;
|
|
} else {
|
|
infoObject = { ...baseInfoObject };
|
|
}
|
|
} else {
|
|
infoObject = typesMetadata.get(typeInfo.type as Constructor | Parsable);
|
|
}
|
|
|
|
if (typeInfo.isArray && !inArray) {
|
|
if ("keyed" in typeInfo.type && typeInfo.type.keyed) {
|
|
const map_old = new Map(obj_old.map((e) => [e.key(), e]));
|
|
const map_new = new Map(obj_new.map((e) => [e.key(), e]));
|
|
|
|
const common_keys = new Set();
|
|
for (const [key, value] of map_old) {
|
|
if (map_new.has(key)) {
|
|
common_keys.add(key);
|
|
result.push(
|
|
...makeDiffSubtree(
|
|
value,
|
|
map_new.get(key),
|
|
`${prefix}/${key}`,
|
|
typesMetadata,
|
|
typeInfo,
|
|
true
|
|
)
|
|
);
|
|
} else {
|
|
result.push(new Diff(prefix, undefined, value));
|
|
}
|
|
}
|
|
|
|
for (const [key, value] of map_new) {
|
|
if (!common_keys.has(key)) {
|
|
result.push(new Diff(prefix, value, undefined));
|
|
}
|
|
}
|
|
} else {
|
|
const array_old: Array<any> = [...obj_old];
|
|
const array_new: Array<any> = [...obj_new];
|
|
array_old.sort();
|
|
array_new.sort();
|
|
while (array_old.length > 0) {
|
|
const head = array_old.shift();
|
|
const new_idx = array_new.indexOf(head);
|
|
if (new_idx !== -1) {
|
|
array_new.splice(new_idx, 1);
|
|
} else {
|
|
result.push(new Diff(prefix, undefined, head));
|
|
}
|
|
}
|
|
result.push(...array_new.map((e) => new Diff(prefix, e, undefined)));
|
|
}
|
|
} else {
|
|
for (const key in infoObject) {
|
|
const key_prefix = `${prefix}/` + (upcast ? `${obj_old.Kind}::${key}` : key);
|
|
if (obj_old[key] === undefined && obj_new[key] !== undefined) {
|
|
result.push(new Diff(`${prefix}/${key}`, obj_new[key].toJSON(), undefined));
|
|
} else if (obj_old[key] !== undefined && obj_new[key] === undefined) {
|
|
result.push(new Diff(`${prefix}/${key}`, undefined, obj_old[key].toJSON()));
|
|
} else if (obj_old[key] === undefined && obj_new[key] === undefined) {
|
|
// No changes, do nothing
|
|
} else if (
|
|
(infoObject[key].ctor == "native" || infoObject[key].ctor == "enum") &&
|
|
!infoObject[key].isArray
|
|
) {
|
|
if (obj_old[key] !== obj_new[key]) {
|
|
result.push(
|
|
new Diff(key_prefix, obj_new[key].toString(), obj_old[key].toString())
|
|
);
|
|
}
|
|
} else if (hasEquals(obj_old[key]) && hasEquals(obj_new[key])) {
|
|
if (!obj_old[key].equals(obj_new[key])) {
|
|
result.push(
|
|
new Diff(key_prefix, obj_new[key].toString(), obj_old[key].toString())
|
|
);
|
|
}
|
|
} else {
|
|
result.push(
|
|
...makeDiffSubtree(
|
|
obj_old[key],
|
|
obj_new[key],
|
|
key_prefix,
|
|
typesMetadata,
|
|
infoObject[key],
|
|
false
|
|
)
|
|
);
|
|
}
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
|
|
function constructType<T>(typeInfo: TypeInfo, data: any): T {
|
|
switch (typeInfo.ctor) {
|
|
case "class":
|
|
return new typeInfo.type(data);
|
|
case "parse":
|
|
return typeInfo.type.parse(data);
|
|
case "enum":
|
|
case "native":
|
|
return typeInfo.type(data);
|
|
}
|
|
}
|
|
|
|
type getTypeInfoType = (path: string | string[], root?: any) => TypeInfo;
|
|
export function _getTypeInfo(
|
|
path: string | string[],
|
|
root: any,
|
|
typesMetadata: TypesMetadata
|
|
): TypeInfo | undefined {
|
|
if (typeof path === "string") {
|
|
path = path.split("/").slice(1);
|
|
}
|
|
|
|
let component = path[0];
|
|
if (component.includes("::")) {
|
|
const parts = component.split("::", 2);
|
|
component = parts[1];
|
|
}
|
|
|
|
const root_hint = typesMetadata.get(root);
|
|
if (root_hint !== undefined && component in root_hint) {
|
|
const type_info = root_hint[component];
|
|
if (path.length === 1) {
|
|
return type_info;
|
|
} else {
|
|
if (type_info.isArray && type_info.ctor === "parse" && "parseKey" in type_info.type) {
|
|
const key = path[1];
|
|
const key_parsed = type_info.type.parseKey(key);
|
|
if ("Kind" in key_parsed) {
|
|
const specialized_type = Array.from(typesMetadata.keys()).find(
|
|
(e) => "name" in e && e["name"] === key_parsed.Kind
|
|
);
|
|
return _getTypeInfo(path.slice(2), specialized_type, typesMetadata);
|
|
}
|
|
return _getTypeInfo(path.slice(2), type_info.type, typesMetadata);
|
|
} else {
|
|
return _getTypeInfo(
|
|
path.slice(type_info.isArray ? 2 : 1),
|
|
type_info.type,
|
|
typesMetadata
|
|
);
|
|
}
|
|
}
|
|
}
|
|
return undefined;
|
|
}
|
|
|
|
function getParentElementByPath<T>(path: string, obj: any): T | undefined {
|
|
const parentPath = path.split("/").slice(1, -1);
|
|
if (parentPath.length > 1) {
|
|
return _getElementByPath(`/${parentPath.join("/")}`, obj);
|
|
} else {
|
|
return obj;
|
|
}
|
|
}
|
|
|
|
export function _validateDiff<T>(obj: T, diffs: DiffSet, getTypeInfo: getTypeInfoType): boolean {
|
|
for (const diff of diffs.Changes) {
|
|
const target = _getElementByPath(diff.Path, obj);
|
|
const info = getTypeInfo(diff.Path);
|
|
if (info.isArray) {
|
|
if (diff.Remove !== undefined) {
|
|
if (target instanceof Array) {
|
|
const array_target = target.find(
|
|
(e) => yaml.stringify(e) === yaml.stringify(diff.Remove)
|
|
);
|
|
if (array_target === undefined) {
|
|
return false;
|
|
}
|
|
} else {
|
|
return false;
|
|
}
|
|
}
|
|
if (diff.Add !== undefined && target instanceof Array) {
|
|
const array_target = target.find(
|
|
(e) => yaml.stringify(e) === yaml.stringify(diff.Add)
|
|
);
|
|
if (array_target !== undefined) {
|
|
return false;
|
|
}
|
|
}
|
|
} else {
|
|
if (
|
|
diff.Remove !== undefined &&
|
|
yaml.stringify(target) !== yaml.stringify(diff.Remove)
|
|
) {
|
|
return false;
|
|
}
|
|
if (diff.Add !== undefined && diff.Remove === undefined && !isNull(target)) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
export function _applyDiff<T>(
|
|
obj: T,
|
|
diffs: DiffSet,
|
|
validateDiff: (obj: T, diffs: DiffSet) => boolean,
|
|
getTypeInfo: getTypeInfoType,
|
|
clone: (obj: T) => T
|
|
): [false] | [true, T] {
|
|
if (!validateDiff(obj, diffs)) {
|
|
return [false];
|
|
}
|
|
const new_obj = clone(obj);
|
|
for (const diff of diffs.Changes) {
|
|
let target = _getElementByPath(diff.Path, new_obj);
|
|
const info = getTypeInfo(diff.Path);
|
|
if (target instanceof Array) {
|
|
if (diff.Remove !== undefined) {
|
|
const idx = target.findIndex(
|
|
(e) => yaml.stringify(e) === yaml.stringify(diff.Remove)
|
|
);
|
|
target.splice(idx, 1);
|
|
}
|
|
|
|
if (diff.Add !== undefined) {
|
|
(target as any).push(constructType(info, diff.Add));
|
|
}
|
|
} else {
|
|
const parent = getParentElementByPath(diff.Path, new_obj)!;
|
|
const element = diff.Path.split("/").reverse()[0];
|
|
true;
|
|
if (diff.Remove !== undefined) {
|
|
parent[element] = undefined;
|
|
}
|
|
if (diff.Add !== undefined && diff.Add !== "") {
|
|
parent[element] = constructType(info, diff.Add);
|
|
}
|
|
}
|
|
}
|
|
|
|
return [true, new_obj];
|
|
}
|
|
|
|
// Type Hinting
|
|
|
|
type Constructor = new (rawObject: any) => any;
|
|
type SimpleParsable = { parse: (rawObject: any) => any };
|
|
type Parsable = SimpleParsable | (SimpleParsable & { parseKey: (key: string) => any });
|
|
type NativeParsable = (rawObject: any) => any;
|
|
|
|
export type TupleTreeType = Constructor | Parsable;
|
|
|
|
interface CommonTypeInfo {
|
|
isArray: boolean;
|
|
isAbstract: boolean;
|
|
}
|
|
|
|
interface ConstructorType extends CommonTypeInfo {
|
|
type: Constructor;
|
|
ctor: "class";
|
|
}
|
|
|
|
interface ParsableType extends CommonTypeInfo {
|
|
type: Parsable;
|
|
ctor: "parse";
|
|
}
|
|
|
|
interface NativeType extends CommonTypeInfo {
|
|
type: NativeParsable;
|
|
ctor: "native";
|
|
}
|
|
|
|
interface EnumDefinition extends CommonTypeInfo {
|
|
type: NativeParsable;
|
|
ctor: "enum";
|
|
possibleValues: readonly string[];
|
|
}
|
|
|
|
export type TypeInfo = ConstructorType | ParsableType | NativeType | EnumDefinition;
|
|
export type TypeInfoObject = { [key: string]: TypeInfo };
|
|
export type TypesMetadata = Map<TupleTreeType, TypeInfoObject>;
|
|
|
|
export function BigIntBuilder(rawObject: any): bigint {
|
|
return BigInt(rawObject);
|
|
}
|