112 lines · cpp
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-exception6//===----------------------------------------------------------------------===//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(Changes))17 return false;18 19 bool Result = ExecuteOneTest(Changes);20 if (!Result)21 FailedTestsCache.insert(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(*it);35 if (!LHS.empty())36 Res.push_back(LHS);37 if (!RHS.empty())38 Res.push_back(RHS);39}40 41DeltaAlgorithm::changeset_ty42DeltaAlgorithm::Delta(const changeset_ty &Changes,43 const changesetlist_ty &Sets) {44 // Invariant: union(Res) == Changes45 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(Set, SplitSets);60 if (SplitSets.size() == Sets.size())61 return Changes;62 63 return Delta(Changes, 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(*it)) {74 changesetlist_ty Sets;75 Split(*it, Sets);76 Res = Delta(*it, Sets);77 return true;78 }79 80 // Otherwise, if we have more than two sets, see if test passes on the81 // complement.82 if (Sets.size() > 2) {83 // FIXME: This is really slow.84 changeset_ty Complement;85 std::set_difference(Changes.begin(), Changes.end(), it->begin(),86 it->end(),87 std::inserter(Complement, Complement.begin()));88 if (GetTestResult(Complement)) {89 changesetlist_ty ComplementSets;90 ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);91 ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());92 Res = Delta(Complement, 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(changeset_ty()))104 return changeset_ty();105 106 // Otherwise run the real delta algorithm.107 changesetlist_ty Sets;108 Split(Changes, Sets);109 110 return Delta(Changes, Sets);111}112