1 //===- subzero/src/IceRangeSpec.cpp - Include/exclude specification -------===//
2 //
3 // The Subzero Code Generator
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief Implements a class for specifying sets of names and number ranges to
12 /// match against. This is specified as a comma-separated list of clauses.
13 /// Each clause optionally starts with '-' to indicate exclusion instead of
14 /// inclusion. A clause can be a name, or a numeric range X:Y, or a single
15 /// number X. The X:Y form indicates a range of numbers greater than or equal
16 /// to X and strictly less than Y. A missing "X" is taken to be 0, and a
17 /// missing "Y" is taken to be infinite. E.g., "0:" and ":" specify the entire
18 /// set.
19 ///
20 /// This is essentially the same implementation as in szbuild.py, except that
21 /// regular expressions are not used for the names.
22 ///
23 //===----------------------------------------------------------------------===//
24
25 #include "IceRangeSpec.h"
26 #include "IceStringPool.h"
27
28 #include <cctype>
29 #include <string>
30 #include <unordered_set>
31 #include <vector>
32
33 namespace Ice {
34
35 bool RangeSpec::HasNames = false;
36
37 namespace {
38
39 /// Helper function to parse "X" or "X:Y" into First and Last.
40 /// - "X" is treated as "X:X+1".
41 /// - ":Y" is treated as "0:Y".
42 /// - "X:" is treated as "X:inf"
43 ///
44 /// Behavior is undefined if "X" or "Y" is not a proper number (since std::stoul
45 /// throws an exception).
46 ///
47 /// If the string doesn't contain 1 or 2 ':' delimiters, or X>=Y,
48 /// report_fatal_error is called.
getRange(const std::string & Token,uint32_t * First,uint32_t * Last)49 void getRange(const std::string &Token, uint32_t *First, uint32_t *Last) {
50 bool Error = false;
51 auto Tokens = RangeSpec::tokenize(Token, RangeSpec::DELIM_RANGE);
52 if (Tokens.size() == 1) {
53 *First = std::stoul(Tokens[0]);
54 *Last = *First + 1;
55 } else if (Tokens.size() == 2) {
56 *First = Tokens[0].empty() ? 0 : std::stoul(Tokens[0]);
57 *Last = Tokens[1].empty() ? RangeSpec::RangeMax : std::stoul(Tokens[1]);
58 } else {
59 Error = true;
60 }
61 if (*First >= *Last) {
62 Error = true;
63 }
64 if (Error) {
65 llvm::report_fatal_error("Invalid range " + Token);
66 }
67 }
68
69 /// Helper function to add one token to the include or exclude set. The token
70 /// is examined and then treated as either a numeric range or a single name.
record(const std::string & Token,RangeSpec::Desc * D)71 void record(const std::string &Token, RangeSpec::Desc *D) {
72 if (Token.empty())
73 return;
74 // Mark that an include or exclude was explicitly given. This affects the
75 // default decision when matching a value that wasn't explicitly provided in
76 // the include or exclude list.
77 D->IsExplicit = true;
78 // A range is identified by starting with a digit or a ':'.
79 if (Token[0] == RangeSpec::DELIM_RANGE || std::isdigit(Token[0])) {
80 uint32_t First = 0, Last = 0;
81 getRange(Token, &First, &Last);
82 if (Last == RangeSpec::RangeMax) {
83 D->AllFrom = std::min(D->AllFrom, First);
84 } else {
85 if (Last >= D->Numbers.size())
86 D->Numbers.resize(Last + 1);
87 D->Numbers.set(First, Last);
88 }
89 } else {
90 // Otherwise treat it as a single name.
91 D->Names.insert(Token);
92 }
93 }
94
95 } // end of anonymous namespace
96
tokenize(const std::string & Spec,char Delimiter)97 std::vector<std::string> RangeSpec::tokenize(const std::string &Spec,
98 char Delimiter) {
99 std::vector<std::string> Tokens;
100 if (!Spec.empty()) {
101 std::string::size_type StartPos = 0;
102 std::string::size_type DelimPos = 0;
103 while (DelimPos != std::string::npos) {
104 DelimPos = Spec.find(Delimiter, StartPos);
105 Tokens.emplace_back(Spec.substr(StartPos, DelimPos - StartPos));
106 StartPos = DelimPos + 1;
107 }
108 }
109 return Tokens;
110 }
111
112 /// Initialize the RangeSpec with the given string. Calling init multiple times
113 /// (e.g. init("A");init("B");) is equivalent to init("A,B"); .
init(const std::string & Spec)114 void RangeSpec::init(const std::string &Spec) {
115 auto Tokens = tokenize(Spec, DELIM_LIST);
116 for (const auto &Token : Tokens) {
117 if (Token[0] == '-') {
118 exclude(Token.substr(1));
119 } else {
120 include(Token);
121 }
122 }
123 if (!Includes.Names.empty() || !Excludes.Names.empty())
124 HasNames = true;
125 }
126
127 /// Determine whether the given Name/Number combo match the specification given
128 /// to the init() method. Explicit excludes take precedence over explicit
129 /// includes. If the combo doesn't match any explicit include or exclude:
130 /// - false if the init() string is empty (no explicit includes or excludes)
131 /// - true if there is at least one explicit exclude and no explicit includes
132 /// - false otherwise (at least one explicit include)
match(const std::string & Name,uint32_t Number) const133 bool RangeSpec::match(const std::string &Name, uint32_t Number) const {
134 // No match if it is explicitly excluded by name or number.
135 if (Excludes.Names.find(Name) != Excludes.Names.end())
136 return false;
137 if (Number >= Excludes.AllFrom)
138 return false;
139 if (Number < Excludes.Numbers.size() && Excludes.Numbers[Number])
140 return false;
141
142 // Positive match if it is explicitly included by name or number.
143 if (Includes.Names.find(Name) != Includes.Names.end())
144 return true;
145 if (Number >= Includes.AllFrom)
146 return true;
147 if (Number < Includes.Numbers.size() && Includes.Numbers[Number])
148 return true;
149
150 // Otherwise use the default decision.
151 return Excludes.IsExplicit && !Includes.IsExplicit;
152 }
153
include(const std::string & Token)154 void RangeSpec::include(const std::string &Token) { record(Token, &Includes); }
155
exclude(const std::string & Token)156 void RangeSpec::exclude(const std::string &Token) { record(Token, &Excludes); }
157
158 } // end of namespace Ice
159