1 | //===- DeltaAlgorithm.h - A Set Minimization Algorithm ---------*- C++ -*--===// |
---|---|

2 | // |

3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |

4 | // See https://llvm.org/LICENSE.txt for license information. |

5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |

6 | //===----------------------------------------------------------------------===// |

7 | |

8 | #ifndef LLVM_ADT_DELTAALGORITHM_H |

9 | #define LLVM_ADT_DELTAALGORITHM_H |

10 | |

11 | #include <set> |

12 | #include <vector> |

13 | |

14 | namespace llvm { |

15 | |

16 | /// DeltaAlgorithm - Implements the delta debugging algorithm (A. Zeller '99) |

17 | /// for minimizing arbitrary sets using a predicate function. |

18 | /// |

19 | /// The result of the algorithm is a subset of the input change set which is |

20 | /// guaranteed to satisfy the predicate, assuming that the input set did. For |

21 | /// well formed predicates, the result set is guaranteed to be such that |

22 | /// removing any single element would falsify the predicate. |

23 | /// |

24 | /// For best results the predicate function *should* (but need not) satisfy |

25 | /// certain properties, in particular: |

26 | /// (1) The predicate should return false on an empty set and true on the full |

27 | /// set. |

28 | /// (2) If the predicate returns true for a set of changes, it should return |

29 | /// true for all supersets of that set. |

30 | /// |

31 | /// It is not an error to provide a predicate that does not satisfy these |

32 | /// requirements, and the algorithm will generally produce reasonable |

33 | /// results. However, it may run substantially more tests than with a good |

34 | /// predicate. |

35 | class DeltaAlgorithm { |

36 | public: |

37 | using change_ty = unsigned; |

38 | // FIXME: Use a decent data structure. |

39 | using changeset_ty = std::set<change_ty>; |

40 | using changesetlist_ty = std::vector<changeset_ty>; |

41 | |

42 | private: |

43 | /// Cache of failed test results. Successful test results are never cached |

44 | /// since we always reduce following a success. |

45 | std::set<changeset_ty> FailedTestsCache; |

46 | |

47 | /// GetTestResult - Get the test result for the \p Changes from the |

48 | /// cache, executing the test if necessary. |

49 | /// |

50 | /// \param Changes - The change set to test. |

51 | /// \return - The test result. |

52 | bool GetTestResult(const changeset_ty &Changes); |

53 | |

54 | /// Split - Partition a set of changes \p S into one or two subsets. |

55 | void Split(const changeset_ty &S, changesetlist_ty &Res); |

56 | |

57 | /// Delta - Minimize a set of \p Changes which has been partitioned into |

58 | /// smaller sets, by attempting to remove individual subsets. |

59 | changeset_ty Delta(const changeset_ty &Changes, |

60 | const changesetlist_ty &Sets); |

61 | |

62 | /// Search - Search for a subset (or subsets) in \p Sets which can be |

63 | /// removed from \p Changes while still satisfying the predicate. |

64 | /// |

65 | /// \param Res - On success, a subset of Changes which satisfies the |

66 | /// predicate. |

67 | /// \return - True on success. |

68 | bool Search(const changeset_ty &Changes, const changesetlist_ty &Sets, |

69 | changeset_ty &Res); |

70 | |

71 | protected: |

72 | /// UpdatedSearchState - Callback used when the search state changes. |

73 | virtual void UpdatedSearchState(const changeset_ty &Changes, |

74 | const changesetlist_ty &Sets) {} |

75 | |

76 | /// ExecuteOneTest - Execute a single test predicate on the change set \p S. |

77 | virtual bool ExecuteOneTest(const changeset_ty &S) = 0; |

78 | |

79 | DeltaAlgorithm& operator=(const DeltaAlgorithm&) = default; |

80 | |

81 | public: |

82 | virtual ~DeltaAlgorithm(); |

83 | |

84 | /// Run - Minimize the set \p Changes by executing \see ExecuteOneTest() on |

85 | /// subsets of changes and returning the smallest set which still satisfies |

86 | /// the test predicate. |

87 | changeset_ty Run(const changeset_ty &Changes); |

88 | }; |

89 | |

90 | } // end namespace llvm |

91 | |

92 | #endif // LLVM_ADT_DELTAALGORITHM_H |

93 |