Abstract:<\/em>
\nFinding the differences between two versions of a source code file is
\na very common operation in software development. It is used in various
\ntasks such as performing a code review or understanding a bug fix.
\nMany automated tools have been introduced over the years to assist the
\ndevelopers in this tedious task. For instance, \\texttt{diff} is very
\nfamous among the developers. This tool consider source code files as a
\nsequence of text lines and find a minimal cost edition sequence that
\ntransform a sequence into another. The actions are: insert a line,
\ndelete a line and update a line.<\/p>\ndiff is very useful: it works without any adaptation on any
\ntextual programming language. Nevertheless, its limitation is very
\nobvious: a source code is not really a sequence of lines, it always
\nhas a tree structure, usually called abstract syntax tree (AST). Many
\napproaches have adapted the idea of textual differencing to trees.
\nThese approaches find an minimal cost edition sequence between two
\ntrees. The editing actions on a tree are: insert a node, delete a node
\nand update the label of a node.<\/p>\n
Unfortunately, the best known algorithms to find such a sequence have
\na $O(n^3)$ time complexity (n beeing the number of nodes), which is
\nexpensive for real world ASTs that contain more than tens of thousands
\nnodes. More importantly, these approaches do not take into account a
\nvery frequent edit action used in software development: moving a node.
\nIf this action is taken into account, the problem of finding an
\nminimal cost edition sequence is NP-hard. AST differencing including
\nmoves requires therefore good heuristics to be used in practice.<\/p>\n
AST differencing including move actions has not been investigated a
\nlot. The main approaches in the literature are either language
\nspecifics and\/or does not work on raw ASTs and\/or have not been
\nempirically validated. We propose a novel algorithm that computes an
\nedition sequence between two ASTs including move actions. This
\nalgorithm is very fast and works on raw ASTs with almost no
\nconfiguration.<\/p><\/div>\n
<\/p>","protected":false},"excerpt":{"rendered":"
On Wednesday 12 December 2012, 9:00-9:30 INRIA Lille room B31 (new building), Jean-R\u00e9my Falleri (Associate Professor @ ENSEIRB-MATMECA) will give a talk on “Understanding Code Changes With AST Differencing” Abstract: Finding the differences between two versions of a source code file is a very common operation in software development. It is used in various … <\/p>\n
Continue reading<\/a><\/p>\n","protected":false},"author":65,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-162","post","type-post","status-publish","format-standard","hentry","category-talk","nodate","item-wrap"],"_links":{"self":[{"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/posts\/162","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/users\/65"}],"replies":[{"embeddable":true,"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/comments?post=162"}],"version-history":[{"count":9,"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/posts\/162\/revisions"}],"predecessor-version":[{"id":225,"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/posts\/162\/revisions\/225"}],"wp:attachment":[{"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/media?parent=162"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/categories?post=162"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/project.inria.fr\/se-seminars\/wp-json\/wp\/v2\/tags?post=162"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}