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