Sites Inria

English version

Séminaire

Séminaire Gallium

  • Date : 12/06/2019
  • Lieu : Salle JLL1
  • Intervenant(s) : Victor Miraldo
  • Organisateur(s) : Equipe-projet Gallium

Lessons from Structural Differencing

Victor Miraldo, Université Utrecht

Structural differencing aims at detecting changes at a smaller granularity than lines of code, as opposed to the UNIX diff, for example. This improved granularity helps in developing better merge functions, that require less human interaction, consequently it is usually more expensive to compute than a regular line-based patch. This talk will go over the implementation of an efficient structural differencing algorithm, focusing on how it differs from
the state-of-the art and the general lessons we can extract from it. Our algorithm works over a novel representation for structured patches, which
enables us to represent arbitrary tree permutations and duplications. Surprisingly, this added expessive power lowers the algorithm's complexity. The final algorithm runs in linear time, making it a competitive approach, in practice.

Haut de page

Suivez Inria