Generating diffs between archives using a generic grammar

1 . A method for generating a diff archive from a source payload file stored in a source archive and a target payload file stored in a target archive, the method comprising:

generating, based on the source archive, a source recipe that, when applied to a copy of the source archive, generates a copy of the source payload file from a plurality of source data chunks stored in the copy of the source archive;

generating a delta recipe that, when applied to the copy of the source payload file, generates a copy of the target payload file;

generating a target recipe that, when applied to the copy of the target payload file, splits the copy of the target payload file into a plurality of target data chunks and stores the plurality of target data chunks in a copy of the target archive;

composing the target recipe, the delta recipe, and the source recipe into a composite recipe;

storing the composite recipe in the diff archive; and

transmitting the diff archive to a computing device, wherein applying the composite recipe of the diff archive causes the computing device to:

apply the source recipe to generate the copy of the source payload file from the plurality of source data chunks stored in the copy of the source archive,

apply the delta recipe to generate the copy of the target payload file from the source payload file, and

apply the target recipe to split the copy of the target payload file into the plurality of target data chunks and store the plurality of target data chunks in the copy of the target payload file.

2 . The method of claim 1 , wherein the computing device is caused to install a software application update from the copy of the target archive.

3 . The method of claim 1 , wherein the source recipe comprises a concatenation recipe that concatenates the plurality of source data chunks into the copy of the source payload file.

4 . The method of claim 1 , wherein the target recipe comprises a region recipe that extracts the plurality of target data chunks from the copy of the target payload file.

5 . The method of claim 1 , wherein the target recipe, the delta recipe, and the source recipe are composed in part by setting a target payload file parameter of the target recipe to the delta recipe, such that the target recipe is applied to an output of the delta recipe.

6 . The method of claim 5 , wherein the target recipe, the delta recipe, and the source recipe are composed in part by setting a source payload file parameter of the delta recipe to the source recipe.

7 . The method of claim 1 , further comprising:

computing a binary delta between the source payload file and the target payload file;

storing the binary delta in the diff archive, wherein applying the composite recipe further causes the computing device is to

apply the binary delta to the copy of the source payload file to create the copy of the target payload file.

8 . The method of claim 6 , wherein the source payload file parameter comprises a first source payload file parameter, and wherein the composite recipe further includes an intermediate recipe with a second source payload file parameter, the method further comprising:

setting the first source payload file parameter of the delta recipe to the intermediate recipe; and

setting the second source payload file parameter of the intermediate recipe to the source recipe.

9 . The method of claim 8 , wherein the intermediate recipe compresses the source payload file, decompresses the source payload file, encrypts the source payload file, decrypts the source payload file, combines the source payload file with other source payload files, or combines a portion of the source payload file with other source payload files.

10 . The method of claim 6 , wherein the target payload file parameter comprises a first target payload file parameter, and wherein the composite recipe further includes an intermediate recipe with a second target payload file parameter, the method further comprising:

setting the first target payload file parameter of the target recipe to the intermediate recipe; and

setting the second target payload file parameter of the intermediate recipe to the delta recipe.

11 . The method of claim 10 , wherein the intermediate recipe decompresses, compresses, decrypts, or encrypts, the output of the delta recipe.

12 . A computing device comprising:

a processor; and

a memory storing computer-executable instructions thereupon which, when executed by the processor, cause the computing device to perform operations comprising:

generate, based on a source archive, a source recipe that, when applied to a copy of the source archive, generates a copy of a source payload file from a plurality of source data chunks stored in the copy of the source archive;

generate a delta recipe that, when applied to the copy of the source payload file, generates a copy of the target payload file;

generate a target recipe that, when applied to the copy of the target payload file, splits the copy of the target payload file into a plurality of target data chunks and stores the plurality of target data chunks in a copy of the target archive;

compose the target recipe, the delta recipe, and the source recipe into a composite recipe;

store the composite recipe in a diff archive; and

transmit the diff archive to a client computing device, causing the client computing device to:

apply the composite recite of the diff archive to generate the copy of the target archive from the copy of the source archive, and

install a software update by applying the copy of the target archive.

13 . The computing device of claim 12 , wherein the computer-executable instructions further cause the computing device to:

determine that the source payload file comprises a sub archive; wherein the source recipe recursively applies a composite diff generation process to to the sub archive.

14 . The computing device of claim 12 , wherein the computer-executable instructions further cause the computing device to:

generate a source archive metadata file that includes a first plurality of data chunk tokens that refer to the plurality of source data chunks; and

generate a target archive metadata file that includes a second plurality of data chunk tokens that refer to the plurality of target data chunks, and wherein an individual data chunk token includes an offset into an archive, a length, and a hash of the corresponding data chunk.

15 . The computing device of claim 14 , wherein the source archive metadata file includes a payload file token that includes a filename of the source payload file and a recipe for generating the source payload file that references one or more of the first plurality of data chunk tokens.

16 . The computing device of claim 14 , wherein the target archive metadata file includes a payload file token that includes a filename of the target payload file and a recipe for generating one or more of the second plurality of data chunk tokens from the target payload file.

17 . The computing device of claim 14 , wherein the source archive metadata file is generated by an archive reader that is specific to a particular archive type, and wherein the archive reader uses information specific to the particular archive type to open the source archive, identify data chunks, and generate the first plurality of data chunk tokens to refer to the identified data chunks.

18 . The computing device of claim 14 , wherein the computer-executable instructions further cause the computing device to:

analyze the target archive and the second plurality of data chunk tokens to identify an unrepresented region of the target archive that is not represented by any of the second plurality of data chunk tokens; and

add a placeholder data chunk token to the second plurality of data chunk tokens, wherein the placeholder data chunk token represents the unrepresented region of the target archive, wherein the placeholder data chunk token causes a region of the copy of the target archive to be created that corresponds to the unrepresented region of the target archive, causing the region of the copy of the target archive to be a byte-for-byte copy of the unrepresented region of the target archive.

19 . A system comprising:

a processor; and

a memory storing computer-executable instructions thereupon which, when executed by the processor, cause the system to perform operations comprising:

receiving a diff archive;

extracting, from the diff archive, a composite recipe that includes a chunk recipe, a binary delta, and a region recipe, wherein the chunk recipe includes a reference to a data chunk stored in a copy of a source archive;

applying the chunk recipe to extract the data chunk from the source archive;

generating a source payload file in part from the extracted data chunk;

extracting, from the diff archive, the binary delta;

applying the binary delta to the generated source payload file to generate a target payload file;

extracting, from the diff archive, the region recipe;

applying the region recipe to generate a target data chunk from the generated target payload file;

generating a target archive that stores the target data chunk;

extracting a copy of the generated target payload file from the target archive; and

installing a software update on a computing device using the extracted copy of the generated target payload file.

20 . The system of claim 19 , wherein the target archive is a subsequent version of the source archive.