Minimizing Database Repros using Language Grammars

• US 20150033206A1
• Filed: 08/11/2014
• Published: 01/29/2015
• Est. Priority Date: 06/14/2010
• Status: Abandoned Application

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Bruno, Nicolas
• Application Number:
  US14/455,994
• Publication Number:
  US 20150033206A1
• Time in Patent Office: Days
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3668 Software testing software testing in telephone exchanges H04M3/242, testing of hardware G06F11/22
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases
• CPC Class Codes: G06F 11/3696 Methods or tools to render software testable
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases

Abstract

Described is automatically processing an initial database repro (text representing a bug when corresponding script is executed in a database engine) into a min-repro (a subset of the text) that is simplified version of the initial repro yet still contains the bug. A parse tree representative of the initial database repro is processed into simplified parse trees based on language grammar rules, e.g., by replacing higher level nodes with descendant nodes. Repros of the simplified parse trees are executed to determine which simplified repros still fail execution because of the bug (that is, the simplified repros were not oversimplified). A minimum simplified parse tree with respect to a desired level of minimality is found from among those failing repros, with the simplified repro that corresponds to the minimum simplified parse tree output as the min-repro.

Claims

1-20. -20. (canceled)

21. In a computing environment, a method performed on at least one processor comprising:

processing a search space of simplifications operative to transform an initial database repro into a set of syntactically valid repros;

pruning the search space based upon monotonicity corresponding to executing a repro of the set of syntactically valid repros to determine whether execution of the repro fails because a bug is present; and

minimizing an initial database repro into a min-repro of which execution fails because the bug is present and a complexity is minimal amongst the set of syntactically valid repros.

22. The method of claim 21 further comprising removing a portion of the repro having at least one label comprising a token of the at least one language grammar rule.

23. The method of claim 21 further comprising executing the repro and if executing the repro fails because of a bug present in the initial database repro, simplifying the repro into a different syntactically valid repro.

24. The method of claim 21 further comprising pruning the search space of syntactically invalid combinations of the simplifications.

25. The method of claim 21, wherein minimizing the initial database repro further comprises:

inputting a parse tree that represents an initial database repro;

simplifying the parse tree into a simplified parse tree by replacing at least one node in the parse tree with another node based on language grammar rules; and

executing a syntactically valid repro corresponding to the simplified parse tree to determine whether execution of the syntactically valid repro fails because of a bug present in the initial database repro.

26. The method of claim 25, wherein if execution of the syntactically valid repro does not fail, simplifying the parse tree into a different simplified parse tree based on the language grammar rules.

27. The method of claim 25, further comprising selecting a different node in the parse tree for simplification after exhausting simplifications for a given node.

28. The method of claim 25 further comprising discarding syntactically invalid combinations of subtrees of the simplified parse tree.

29. The method of claim 21 further comprising if executing syntactically valid repro fails because of a semantic error, pruning a portion of the search space that corresponds to descendants of the simplified parse tree.

30. The method of claim 29 further comprising simplifying the syntactically valid repro into a simplified repro that is syntactically correct and semantically valid.

31. The method of claim 21 further comprising determining the set of syntactically valid repros based at least partially on language grammar rules for the initial database repro.

32. In a computing environment, a method performed on at least one processor comprising:

performing at least one simplification on a database repro, the at least one simplification corresponding to at least one language grammar rule;

processing a database engine to execute a simplified version of the database repro to determine whether a bug manifests for the database repro; and

outputting the simplified version of the database repro as a min-repro.

33. The method of claim 32 further comprising generating a rule corresponding to at least one of a language grammar pattern or a domain-specific optimization.

34. The method of claim 32 further comprising generating at least one of a rule to prevent at least one simplification from being applied or a rule to apply a simplification that is not based upon language grammar rules.

35. The method of claim 32 further comprising disabling a rule in the language grammar rules.

36. The method of claim 32 further comprising replacing right-hand side of the at least one language grammar rule with a valid alternative.

37. In a computing environment, an apparatus comprising:

a language grammar minimizing mechanism operative to minimize an initial database repro into a min-repro in which a bug in the initial database repro manifests for the min-repro, the language grammar minimizing mechanism further operative to process a search space of simplifications to transform the initial database repro into a set of repros that are syntactically correct according to at least one language grammar rule and process the set of repros to determine the min-repro.

38. The apparatus of claim 37, wherein the language grammar minimizing mechanism to instruct a database engine to test at least one of the set of repros.

39. The apparatus of claim 37, wherein the language grammar minimizing mechanism to eliminate invalid repros from the search space of simplifications.

40. The apparatus of claim 37, wherein the language grammar minimizing mechanism to execute repro having a 1-minimal complexity amongst the set of repros.