Diffing prior executions of an executable program

A computer system for diffing prior executions of an executable program, comprising:

• a processor;
• and
• a computer storage medium that stores computer-executable instructions that are executable by the processor to at least:
• identify a first ordered set comprising a first plurality of entities obtained from a first trace of a first execution context of the executable program, and identify a second ordered set comprising a second plurality of entities obtained from a second trace of a second execution context of the executable program;
• assign a weighting to each entity type in the first plurality of entities and the second plurality of entities, including at least assigning a first weighting to a first entity type and assigning a second weighting to a second entity type, the first weighting being different than the second weighting;
• calculate an edit distance between the first ordered set and the second ordered set, including,
• creating a diffing structure from the first ordered set and the second ordered set;
• and
• calculating a minimal cost path through the diffing structure, the minimal cost path starting at a first entry representing an intersection between an empty first ordered set and an empty second ordered set, and ending at a second entry representing an intersection between an entire first ordered set and an entire second ordered set, the edit distance being based on a calculated cost at the second entry, calculating the minimal cost path including, for at least two iterations,
• (a) identifying a partition of the diffing structure based on identifying an intersecting entry in the diffing structure that corresponds to a local optimal, wherein,
• the intersecting entry is an entry or exit point of the partition and is selected based on (i) only permitting replacements between entities in the first ordered set and the second ordered set that have a common entity type, and (ii) utilizing at least a difference between the first weighting and the second weighting to identify a single-entity replacement across the first ordered set and the second ordered set that has a higher replacement cost than an adjoining multi-entity replacement across the first ordered set and the second ordered set;
• and
• the intersecting entry dominates at least one of (i) a first predicted cost calculated based on comparing a first subset of the first ordered set that precedes the intersecting entry and a first subset of the second ordered set that precedes the intersecting entry, or (ii) a second predicted cost calculated based on comparing a second subset of the first ordered set that is after the intersecting entry and a second subset of the second ordered set that is after the intersecting entry;
• and
• (b) applying a differencing algorithm to the partition, to identify a corresponding segment of the minimal cost path, the corresponding segment beginning or ending with the intersecting entry;
• and
• output the edit distance to a software component or to an other computer system, and which causes the software component or to the other computer system to operate on the edit distance.

A computer-readable hardware storage medium that stores computer-executable instructions that are executable by a processor system to at least:

• identify a first ordered set comprising a first plurality of entities obtained from a first trace of a first execution context of an executable program, and identify a second ordered set comprising a second plurality of entities obtained from a second trace of a second execution context of the executable program;
• assign a weighting to each entity type in the first plurality of entities and the second plurality of entities, including at least assigning a first weighting to a first entity type and assigning a second weighting to a second entity type, the first weighting being different than the second weighting;
• calculate an edit distance between the first ordered set and the second ordered set, including,
• creating a diffing structure from the first ordered set and the second ordered set;
• and
• calculating a minimal cost path through the diffing structure, the minimal cost path starting at a first entry representing an intersection between an empty first ordered set and an empty second ordered set, and ending at a second entry representing an intersection between an entire first ordered set and an entire second ordered set, the edit distance being based on a calculated cost at the second entry, calculating the minimal cost path including, for at least two iterations,
• (a) identifying a partition of the diffing structure based on identifying an intersecting entry in the diffing structure that corresponds to a local optimal, wherein,
• the intersecting entry is an entry or exit point of the partition and is selected based on (i) only permitting replacements between entities in the first ordered set and the second ordered set that have a common entity type, and (ii) utilizing at least a difference between the first weighting and the second weighting to identify a single-entity replacement across the first ordered set and the second ordered set that has a higher replacement cost than an adjoining multi-entity replacement across the first ordered set and the second ordered set;
• and
• the intersecting entry dominates at least one of (i) a first predicted cost calculated based on comparing a first subset of the first ordered set that precedes the intersecting entry and a first subset of the second ordered set that precedes the intersecting entry, or (ii) a second predicted cost calculated based on comparing a second subset of the first ordered set that is after the intersecting entry and a second subset of the second ordered set that is after the intersecting entry;
• and
• (b) applying a differencing algorithm to the partition, to identify a corresponding segment of the minimal cost path, the corresponding segment beginning or ending with the intersecting entry;
• and
• output the edit distance to a software component or to an other computer system, and which causes the software component or to the other computer system to operate on the edit distance.