3The tool works by simultaneously looking at a pair of nodes in OpenAPI schema
4trees. At every place we try to understand whether one side (the producer) can
5produce something that the other side (the consumer) cannot consume. This often
6involves recursively running the same check on child sub-nodes. The necessary
7criteria are implemented manually for all types of nodes that appear in the
8schema. The `Subtree` class in `Data.OpenApi.Compare.Subtree` designates types
9of nodes for which this compatibility checking is defined. The implementations
10for various types reside in `Data.OpenApi.Compare.Validate.*`.
14Rather than looking at which schema is the server's and which is the client's,
15in terms of compatibility checking it is more useful to track which side is the
16"producer" and which is the "consumer". At the root of the schema the producer
17is the client, but as we descend into an HTTP response, the direction flips and
18the producer becomes the server.
20We deal with a lot of things in pairs, where one thing belongs to the producer
21and another belongs to the consumer. The `ProdCons` datatype (in
22`Data.OpenApi.Compare.Subtree`) is just a pair type that provides an Applicative
23abstraction for working with two things simultaneously.
27We directly use the datatypes defined in the `openapi3` library. For reasons of
28identifiability and memoization we tag all nodes in the trees with a path from
29the root. The tree is heterogeneous (nodes have different types), and every type
30of node has a different arrangement of children. There is a `Step` data family
31that defines all the possible children (of a specific type) of a node (of a
34A `Trace` is a sequence of steps, except in a path the types of adjacent steps
35have to agree. The `Paths` datatype achieves this. Together all paths form a
36`Category`, and we often concatenate them using `>>>`. This is defined in
37`Data.OpenApi.Compare.Paths`.
39We often keep a node and a path to it next to each other using an environment
40comonad. `Traced` is a type alias around `Env` which ensures that the type of
41the path matches the type of the node.
45The output of the tool is a list of compatibility issues that came up during
46checking. The `Issue` data family describes the kinds of issues that can occur
47at each type of node. An issue is supposed to characterize a set of interactions
48(requests or responses) that demonstrate that the schemas are incompatible.
50Each issue is tagged with a `Behavior` that describes the path to reproducing
51the issue. While a `Trace` describes a syntactic path down the schema tree, a
52`Behavior` describes which part of an interaction needs to be focused on for the
53issue to manifest itself.
55In most places where we keep multiple issues (e.g. the output), to store them we
56use a prefix tree map, indexed by both types and values of `Behavior`s. See
57`Data.OpenApi.Compare.PathsPrefixTree`.
61The checker ultimately outputs a list of `Issue`s, together with `Behavior`s
62that cause them. We run the checker twice: forwards and backwards -- to detect
63non-breaking changes. All of this is then compiled into a report in
64`Data.OpenApi.Compare.Report`. The tree structure of headings is computed from
65`Behavior`s, using `Jet`s to collapse particular sequences of behavior steps
66into a single human-readable header item. The text of each paragraph comes from
69We then use the `pandoc` library to render the report in a variety of formats.
73The schema has references, so it can end up being recursive. Similarly the
74process for establishing compatibility can end up being recursive. To keep track
75of this, the checker actually manipulates *formulas* which can have variables in
76them, defined in (`Data.OpenApi.Compare.Formula`).
78A formula represents a set of issues, with the empty set corresponding to a
79successful compatibility check. A formula can have conjunctions, where we only
80report success if all parts succeeded, and if not we take the union of all
81issues. A formula can also have disjunctions, but there it's impossible to
82guarantee that the issues for the parts also make sense as issues for the whole
83thing. Due to this if all disjuncted parts have issues we instead return a
84different issue (usually non-descriptive).
86The `FormulaF` datatype implements a functor that carries formulaic calculations
87as well as a result value (a co-Yoneda extension of formulas for the most part).
88The Applicative interface provides conjunction, and the Alternative interface
91When we detect recursion we introduce a variable, compute the compatibility
92check as a formula with that variable, and then we solve a fixed point equation
93(`maxFixpoint`) with the variable to obtain the answer.
95This `FomulaF` is further wrapped in a couple monad transformers
96(`SemanticCompatFormula`, `StructuralCompatFormula`), and the whole checker is
97then implemented in the resulting Applicative using ApplicativeDo.
101The `Data.OpenApi.Compare.Memo` module contains utilities for stateful
102memoization and recursion detection. The entire checking process is memoized,
103and can detect, propagate, and resolve recursion.
105Structural/Semantic Compatibility
106---------------------------------
107When we encounter two nodes we first try to optimistically establish whether
108they're structurally equal, i.e. the trees are exactly the same modulo reference
109inlining. This check is also memoized and recursion-aware. If the check succeeds
110we conclude that the schemas are compatible. Otherwise we fall back to the
111"normal" semantic compatibility.
116The language that describes JSON payloads is probably the richest part of
117OpenAPI schemas, and the checker for it also comes with a lot of moving parts.
119JSON schema allows arbitrary set arithmetic using `allOf`, `anyOf`, `not` and
120`oneOf`. To fully check `not` and `oneOf` we would need to compare set
121subtraction, which involves negating a comparison result. If recursion is
122involved we would need to be able to solve equations with negation, which we
123cannot do. So `not` is unsupported altogether, and `oneOf` is only supported
124when it has disjoint branches and behaves like `anyOf`.
126With that in mind a JSON schema is first pre-processed into a Disjunctive Normal
127Form (`DNF` in `Data.OpenApi.Compare.Validate.Schema.DNF`). This pre-processing
128happens in `Data.OpenApi.Compare.Validate.Schema.Process`.
130The DNF contains elementary clauses that match on a specific aspect of a JSON
131object (`Condition`). Most clauses only affect objects of a single type, so JSON
132values and clauses are segregated by type (`JsonType`, `TypedValue` in
133`Data.OpenApi.Compare.Validate.Schema.JsonFormula`)
135Then we reduce the problem of comparing two DNF's to the comparison of a
136conjunction of clauses in the producer with a single clause in the consumer
137(`checkFormulas` in `Data.OpenApi.Compare.Validate.Schema`).
139When we do disjunction in the formula we lose information, so we try to avoid
140having disjunctions in the consumer DNF. This is done by the means of
141partitioning. We look for factors that would let us partition the set of all
142objects into several bins, in a way that hopefully corresponds only a single
143consumer to each producer. This is implemented in
144`Data.OpenApi.Compare.Validate.Schema.Partition`. Currently we can only
145partition by an `enum` value that is accessible via a chain of `required`
148The same partitioning mechanism is used to test whether the branches of a
149`oneOf` are disjoint, and emit a warning otherwise.
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list