1//===--- DeltaAlgorithm.cpp - 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#include "llvm/ADT/DeltaAlgorithm.h"
9#include <algorithm>
10#include <iterator>
11using namespace llvm;
12
13DeltaAlgorithm::~DeltaAlgorithm() = default;
14
15bool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
16 if (FailedTestsCache.count(x: Changes))
17 return false;
18
19 bool Result = ExecuteOneTest(S: Changes);
20 if (!Result)
21 FailedTestsCache.insert(x: Changes);
22
23 return Result;
24}
25
26void DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) {
27 // FIXME: Allow clients to provide heuristics for improved splitting.
28
29 // FIXME: This is really slow.
30 changeset_ty LHS, RHS;
31 unsigned idx = 0, N = S.size() / 2;
32 for (changeset_ty::const_iterator it = S.begin(),
33 ie = S.end(); it != ie; ++it, ++idx)
34 ((idx < N) ? LHS : RHS).insert(x: *it);
35 if (!LHS.empty())
36 Res.push_back(x: LHS);
37 if (!RHS.empty())
38 Res.push_back(x: RHS);
39}
40
41DeltaAlgorithm::changeset_ty
42DeltaAlgorithm::Delta(const changeset_ty &Changes,
43 const changesetlist_ty &Sets) {
44 // Invariant: union(Res) == Changes
45 UpdatedSearchState(Changes, Sets);
46
47 // If there is nothing left we can remove, we are done.
48 if (Sets.size() <= 1)
49 return Changes;
50
51 // Look for a passing subset.
52 changeset_ty Res;
53 if (Search(Changes, Sets, Res))
54 return Res;
55
56 // Otherwise, partition the sets if possible; if not we are done.
57 changesetlist_ty SplitSets;
58 for (const changeset_ty &Set : Sets)
59 Split(S: Set, Res&: SplitSets);
60 if (SplitSets.size() == Sets.size())
61 return Changes;
62
63 return Delta(Changes, Sets: SplitSets);
64}
65
66bool DeltaAlgorithm::Search(const changeset_ty &Changes,
67 const changesetlist_ty &Sets,
68 changeset_ty &Res) {
69 // FIXME: Parallelize.
70 for (changesetlist_ty::const_iterator it = Sets.begin(),
71 ie = Sets.end(); it != ie; ++it) {
72 // If the test passes on this subset alone, recurse.
73 if (GetTestResult(Changes: *it)) {
74 changesetlist_ty Sets;
75 Split(S: *it, Res&: Sets);
76 Res = Delta(Changes: *it, Sets);
77 return true;
78 }
79
80 // Otherwise, if we have more than two sets, see if test passes on the
81 // complement.
82 if (Sets.size() > 2) {
83 // FIXME: This is really slow.
84 changeset_ty Complement;
85 std::set_difference(first1: Changes.begin(), last1: Changes.end(), first2: it->begin(),
86 last2: it->end(),
87 result: std::inserter(x&: Complement, i: Complement.begin()));
88 if (GetTestResult(Changes: Complement)) {
89 changesetlist_ty ComplementSets;
90 ComplementSets.insert(position: ComplementSets.end(), first: Sets.begin(), last: it);
91 ComplementSets.insert(position: ComplementSets.end(), first: it + 1, last: Sets.end());
92 Res = Delta(Changes: Complement, Sets: ComplementSets);
93 return true;
94 }
95 }
96 }
97
98 return false;
99}
100
101DeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) {
102 // Check empty set first to quickly find poor test functions.
103 if (GetTestResult(Changes: changeset_ty()))
104 return changeset_ty();
105
106 // Otherwise run the real delta algorithm.
107 changesetlist_ty Sets;
108 Split(S: Changes, Res&: Sets);
109
110 return Delta(Changes, Sets);
111}
112