Resolving conflicts in structured file formats

Mentors: Etienne Millon, Ulysse Gérard

Location: Tarides office, Paris

Tracking versions of different source files is one of the day-to-day activities in software development. In particular it is often required to update a particular patch on top of a different version. This can cause git conflicts that need to be resolved by the programmer. In the general case, it is not possible to automatically resolve the conflict, because it corresponds to reasoning on run-time properties of arbitrary programs. However, it is possible to restrict the input language and find a useful decidable subset.

For example, consider dune files. If branch A adds a dependency and branch B adds another dependency, a correct conflict resolution is to add both dependencies in the merged branch. Or if both branches each add a rule, it is possible to merge the changes by adding both rules. A review step is always necessary, so there are some user interface concerns as well.

The goal of this project is to consider file formats used in the OCaml platform (e.g. dune files, opam files) and find ways to:

  • Present conflicts in a structured way (as opposed to the line-based way that git uses)
  • Identify some common conflict classes that can be automatically resolved
  • Present the results so that they can reviewed and accepted or rejected (and in that case fall back to manual resolution)

Different kinds of follow-up work are possible:

  • Making dune files more inspectable. As of dune 2.7, there is no AST or grammar for dune files, which makes some tasks like formatting or syntax highlighting not as precise as they could be.
  • Improving the UI so that this conflict resolution can be done in various editors
  • Extending this kind of work to simple cases on OCaml code (add/add in toplevel open declarations or in list literals, etc.)
For more information and to apply, please email etienne@tarides.com.