1 | //===- DAGDeltaAlgorithm.h - A DAG 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_DAGDELTAALGORITHM_H |

9 | #define LLVM_ADT_DAGDELTAALGORITHM_H |

10 | |

11 | #include <set> |

12 | #include <utility> |

13 | #include <vector> |

14 | |

15 | namespace llvm { |

16 | |

17 | /// DAGDeltaAlgorithm - Implements a "delta debugging" algorithm for minimizing |

18 | /// directed acyclic graphs using a predicate function. |

19 | /// |

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

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

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

23 | /// removing any single element not required by the dependencies on the other |

24 | /// elements would falsify the predicate. |

25 | /// |

26 | /// The DAG should be used to represent dependencies in the changes which are |

27 | /// likely to hold across the predicate function. That is, for a particular |

28 | /// changeset S and predicate P: |

29 | /// |

30 | /// P(S) => P(S union pred(S)) |

31 | /// |

32 | /// The minimization algorithm uses this dependency information to attempt to |

33 | /// eagerly prune large subsets of changes. As with \see DeltaAlgorithm, the DAG |

34 | /// is not required to satisfy this property, but the algorithm will run |

35 | /// substantially fewer tests with appropriate dependencies. \see DeltaAlgorithm |

36 | /// for more information on the properties which the predicate function itself |

37 | /// should satisfy. |

38 | class DAGDeltaAlgorithm { |

39 | virtual void anchor(); |

40 | |

41 | public: |

42 | using change_ty = unsigned; |

43 | using edge_ty = std::pair<change_ty, change_ty>; |

44 | |

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

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

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

48 | |

49 | public: |

50 | virtual ~DAGDeltaAlgorithm() = default; |

51 | |

52 | /// Run - Minimize the DAG formed by the \p Changes vertices and the |

53 | /// \p Dependencies edges by executing \see ExecuteOneTest() on subsets of |

54 | /// changes and returning the smallest set which still satisfies the test |

55 | /// predicate and the input \p Dependencies. |

56 | /// |

57 | /// \param Changes The list of changes. |

58 | /// |

59 | /// \param Dependencies The list of dependencies amongst changes. For each |

60 | /// (x,y) in \p Dependencies, both x and y must be in \p Changes. The |

61 | /// minimization algorithm guarantees that for each tested changed set S, |

62 | /// \f$ x \in S \f$ implies \f$ y \in S \f$. It is an error to have cyclic |

63 | /// dependencies. |

64 | changeset_ty Run(const changeset_ty &Changes, |

65 | const std::vector<edge_ty> &Dependencies); |

66 | |

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

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

69 | const changesetlist_ty &Sets, |

70 | const changeset_ty &Required) {} |

71 | |

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

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

74 | }; |

75 | |

76 | } // end namespace llvm |

77 | |

78 | #endif // LLVM_ADT_DAGDELTAALGORITHM_H |

79 |