Changes to the AST

[timakro]

Hey Lens Community,

we are proposing changes to the structure of the AST with the goal of making the TypeScript definitions in lens stricter and documenting the AST better. Consumers of the AST in strictly typed languages like Rust will benefit as well because they can parse the AST into the stricter typed and more fine-grained data structures, which reduces the need for manual validation in the codebase and benefits readability.

The TypeScript definition of the AST currently looks like this:

export type AstElement = AstTopLayer | AstBottomLayerValue;

export type AstTopLayer = {
    nodeType: "branch";
    key?: string;
    operand: "AND" | "OR";
    children: AstElement[];
};

export type AstBottomLayerValue = {
    nodeType: "leaf";
    key: string;
    type: string;
    system?: string;
    value:
        | string
        | boolean
        | Array<string>
        | { min: number; max: number }
        | { min: string; max: string }; // for dates
};

@patrickskowronekdkfz and I came up with the following in a call today:

// Discuss: I'm not 100% sold on representing the empty query like this.
// Maybe we can come up with something better?
export type Ast = AstNode | { "type": "Empty" }

// The @discriminator annotation tells ts-json-schema-generator to represent
// this type as a discriminated union in the generated JSON schema.
/** @discriminator type */
export type AstNode = AndOperator | OrOperator | NotOperator | NumericRangeFilter | DateRangeFilter | EqualsFilter | AnyFilter;

export type AndOperator = {
    type: "AndOperator";
    /** @minItems 1 */
    operands: AstNode[];
}

export type OrOperator = {
    type: "OrOperator";
    /** @minItems 1 */
    operands: AstNode[];
}

export type NotOperator = {
    type: "NotOperator";
    operand: AstNode;
}

export type NumericRangeFilter = {
    type: "NumericRangeFilter";
    key: string;
    system?: string;
    // Discuss: we also need to support "greater than" and "less than"
    // semantics. Should min and max be optional like shown here, or should this
    // be expressed differently?
    min?: number;
    max?: number;
}

export type DateRangeFilter = {
    type: "DateRangeFilter";
    key: string;
    system?: string;
    /** The earliest accepted date in YYYY-MM-DD format. @format date */
    min?: string;
    /**The latest accepted date in YYYY-MM-DD format. @format date */
    max?: string;
}

export type EqualsFilter = {
    type: "EqualsFilter";
    key: string;
    system?: string;
    value: string;
}

// This corresponds to Array<string> in the old type definition.
// Discuss: is this required or even currently used?
export type AnyFilter = {
    type: "AnyFilter";
    key: string;
    system?: string;
    values: string[];
}

An example in JSON as it would be sent over the wire:

{
  "type": "OrOperator",
  "operands": [
    {
      "type": "AndOperator",
      "operands": [
        {
          "type": "NumericRangeFilter",
          "key": "age",
          "min": 5,
          "max": 10
        }
      ]
    }
  ]
}

Note that nothing here should be seen as set in stone and the final shape of the AST is still very much up for discussion. Features that the proposed representation has and we would like to keep include:

• The union type is a tagged union with the discriminator type and variants are in CamelCase. This makes it very ergonomic to work with in TypeScript and also Rust's serde.
• What was previously AstBottomLayerValue has been split into multiple types, meaning that nonsensical ASTs like {"type": "BETWEEN", "value": "a rock"} can no longer be represented.

We plan to add JSDoc to each node type to document its semantics. Personally I would hope to see the JSDoc converted to HTML at some point to provide as documentation to our users. Optionally we could automatically generate a JSON schema definition from TypeScript using ts-json-schema-generator like we will be doing for the catalogue soon. I've already added appropriate annotations (e.g. @format date) where constraints cannot be expressed in TypeScript.

If you have other suggestions feel free to bring them into the discussion. We would introduce the AST Structure with the next major update of lens with milestone v0.5.

[enola-dkfz]

if you call operands operands you should call operators operators (or operations, that also works)

[timakro]

I think that makes it clearer, updated it in the post.

[enola-dkfz]

It doesn't make it clearer because Operator in the "type" name is pleonasm
instead the field you put operator in should be named "operator"
or don't call the field containing operands "operands"
one without the other makes no sense

[TKussel]

The "type" fields currently denote different things. I would suggest to rename the different "types" to, e.g. "operator" and "filter".
Additionaly, we need to specify how the date strings are formatted, e.g. ISO8601. And what is expected with decreased precision, e.g. "year of diagnosis".

[TKussel]

Only answering on the date subject: the specification you referenced allows RFC 3339 5.6 dates, which themself refence ISO8601 (including the T and Z timezone specifiers, if differing from UTC). It imposes some restrictions, e.g., no hour 24.
Still, I think we would need to specify the exact intended format.

[enola-dkfz]

This is not about Rust! I can absolutely deserialise it into something appropriate, but I will still see what you actually sent me. As will everyone who reads Lens documentation, or Lens paper.

[timakro]

@TKussel The JSON schema spec refers to the "full-date" definition from the RFC you mentioned which does not include a time zone and is exactly equivalent to YYYY-MM-DD. If that is actually what we want I'm not sure. It is how things currently work but as Enola pointed out it is ambiguous without a time zone.

[timakro]

@enola-dkfz I see your point and I see that serde can also handle untagged unions by trying to match against each variant and picking the first that fits (this is what focus does currently). Tagged unions still have advantages though. Maybe we can come up with something that is closer to the representation currently in focus, namely having an outer enum that distinguishes operation vs. filter and then an operation enum that distinguishes between the different operations and a filter enum that distinguishes between the different filters. So in short three enums instead of one.

[enola-dkfz]

Let's sleep on it

[TKussel]

In an in-person meeting @timakro, @enola-dkfz, and I discussed the proposal especially w.r.t. consumers of the AST. We have a slighly modified proposal, as stated below.

We did not discuss empty queries, yet. We did not discuss naming of things (e.g., should it be "operands" or "children"...), but only focused on the structure of the AST.

High level discussion points:

• It is usually harder to consume the AST than to produce it, so for some things we opted for the way that is easier to handle for a consumer (e.g., for disallowing two empty optional range fields).
• We opted to not separate operators and filters in disjoint enum types, as it would incur a functually unnessecary level of hierachy in the AST
• We observed, that equality operations are only nessecary for categorial values, esp. no floating point values. The quirks of IEEE 754 are not relevant here 🎉
• All ranges are specified as inclusive
• We might need to specify units of measurements/LOINC codes in numeric ranges.
• Dates now include time and timezone information to allow sensible and non-surprising usage across timezone and even date borders. For the local time, Lens should use the browser timezone information.
• On of EqualsFilter and AnyFilter is redundant, either the AnyFilter can be built by oring many EqualsFilters, or the EqualsFilter can be built by having only one entry in the "values" array. We opted for the latter to keep the AST small.

Please correct me if I missed something or messed something up :)

// The @discriminator annotation tells ts-json-schema-generator to represent
// this type as a discriminated union in the generated JSON schema.
/** @discriminator type */
export type AstNode = AndOperator | OrOperator | NotOperator | NumericRangeFilter | DateRangeFilter | AnyFilter;

export type AndOperator = {
    type: "AndOperator";
    /** @minItems 1 */
    operands: AstNode[];
}

export type OrOperator = {
    type: "OrOperator";
    /** @minItems 1 */
    operands: AstNode[];
}

export type NotOperator = {
    type: "NotOperator";
    operand: AstNode;
}

export type NumericRangeFilter = {
    type: "NumericRangeFilter";
    key: string;
    // The system could be used to include units of measurement, LOINC codes and so on.
    system?: string;
    // Using optionals for half open intervals is fine, however, at least one entry must be set
    // Ranges are always specified to be inclusive
    min?: number;
    max?: number;
}

export type DateRangeFilter = {
    type: "DateRangeFilter";
    key: string;
    // Note: System was removed here
    // Note: The dates are now specified as "date-time"s as in RFC 3339 sec. 5.6.
    //       For querying, Lens should deduce the local timezone from the browser of the user
    // Ranges are always specified to be inclusive
    /** The earliest accepted date in YYYY-MM-DDTHH:MM:SSZ±OO format. @format date-time */
    min?: string;
    /**The latest accepted date in YYYY-MM-DDTHH:MM:SSZ±OO format. @format date-time */
    max?: string;
}

// This Filter is used for checking set membership. Equality of conditions is a special case with
// only one entry in the "values" array.
export type AnyFilter = {
    type: "AnyFilter";
    key: string;
    system?: string;
    values: string[];
}

[enola-dkfz]

AnyFilter has so far only been used with code systems and therefore only needs strings. We have discussed a potential usage of it with numerical values. It is not unheard of that a membership in a set of distinct numerical values is a criterion of inclusion.