1/*
2 * Copyright (c) 2015-2017, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** \file
30 * \brief Utility functions for working with Report ID sets.
31 */
32#include "ng_reports.h"
33
34#include "ng_holder.h"
35#include "util/container.h"
36#include "util/compile_context.h"
37#include "util/graph_range.h"
38#include "util/report_manager.h"
39
40using namespace std;
41
42namespace ue2 {
43
44/** Returns the set of all reports in the graph. */
45set<ReportID> all_reports(const NGHolder &g) {
46 set<ReportID> rv;
47 for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
48 insert(&rv, g[v].reports);
49 }
50 for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
51 insert(&rv, g[v].reports);
52 }
53
54 return rv;
55}
56
57/** True if *all* reports in the graph are exhaustible. */
58bool can_exhaust(const NGHolder &g, const ReportManager &rm) {
59 for (ReportID report_id : all_reports(g)) {
60 if (rm.getReport(report_id).ekey == INVALID_EKEY) {
61 return false;
62 }
63 }
64
65 return true;
66}
67
68void set_report(NGHolder &g, ReportID internal_report) {
69 // First, wipe the report IDs on all vertices.
70 for (auto v : vertices_range(g)) {
71 g[v].reports.clear();
72 }
73
74 // Any predecessors of accept get our id.
75 for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
76 g[v].reports.insert(internal_report);
77 }
78
79 // Same for preds of acceptEod, except accept itself.
80 for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
81 if (v == g.accept) {
82 continue;
83 }
84 g[v].reports.insert(internal_report);
85 }
86}
87
88/** Derive a maximum offset for the graph from the max_offset values of its
89 * reports. Returns MAX_OFFSET for inf. */
90u64a findMaxOffset(const NGHolder &g, const ReportManager &rm) {
91 u64a maxOffset = 0;
92 set<ReportID> reports = all_reports(g);
93 assert(!reports.empty());
94
95 for (ReportID report_id : all_reports(g)) {
96 const Report &ir = rm.getReport(report_id);
97 if (ir.hasBounds()) {
98 maxOffset = max(maxOffset, ir.maxOffset);
99 } else {
100 return MAX_OFFSET;
101 }
102 }
103 return maxOffset;
104}
105
106} // namespace ue2
107