1 //===- StringMatcher.cpp - Generate a matcher for input strings -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the StringMatcher class.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/TableGen/StringMatcher.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/Support/raw_ostream.h"
25 /// FindFirstNonCommonLetter - Find the first character in the keys of the
26 /// string pairs that is not shared across the whole set of strings. All
27 /// strings are assumed to have the same length.
29 FindFirstNonCommonLetter(const std::vector
<const
30 StringMatcher::StringPair
*> &Matches
) {
31 assert(!Matches
.empty());
32 for (unsigned i
= 0, e
= Matches
[0]->first
.size(); i
!= e
; ++i
) {
33 // Check to see if letter i is the same across the set.
34 char Letter
= Matches
[0]->first
[i
];
36 for (unsigned str
= 0, e
= Matches
.size(); str
!= e
; ++str
)
37 if (Matches
[str
]->first
[i
] != Letter
)
41 return Matches
[0]->first
.size();
44 /// EmitStringMatcherForChar - Given a set of strings that are known to be the
45 /// same length and whose characters leading up to CharNo are the same, emit
46 /// code to verify that CharNo and later are the same.
48 /// \return - True if control can leave the emitted code fragment.
49 bool StringMatcher::EmitStringMatcherForChar(
50 const std::vector
<const StringPair
*> &Matches
, unsigned CharNo
,
51 unsigned IndentCount
, bool IgnoreDuplicates
) const {
52 assert(!Matches
.empty() && "Must have at least one string to match!");
53 std::string
Indent(IndentCount
* 2 + 4, ' ');
55 // If we have verified that the entire string matches, we're done: output the
57 if (CharNo
== Matches
[0]->first
.size()) {
58 if (Matches
.size() > 1 && !IgnoreDuplicates
)
59 report_fatal_error("Had duplicate keys to match on");
61 // If the to-execute code has \n's in it, indent each subsequent line.
62 StringRef Code
= Matches
[0]->second
;
64 std::pair
<StringRef
, StringRef
> Split
= Code
.split('\n');
65 OS
<< Indent
<< Split
.first
<< "\t // \"" << Matches
[0]->first
<< "\"\n";
68 while (!Code
.empty()) {
69 Split
= Code
.split('\n');
70 OS
<< Indent
<< Split
.first
<< "\n";
76 // Bucket the matches by the character we are comparing.
77 std::map
<char, std::vector
<const StringPair
*>> MatchesByLetter
;
79 for (unsigned i
= 0, e
= Matches
.size(); i
!= e
; ++i
)
80 MatchesByLetter
[Matches
[i
]->first
[CharNo
]].push_back(Matches
[i
]);
83 // If we have exactly one bucket to match, see how many characters are common
84 // across the whole set and match all of them at once.
85 if (MatchesByLetter
.size() == 1) {
86 unsigned FirstNonCommonLetter
= FindFirstNonCommonLetter(Matches
);
87 unsigned NumChars
= FirstNonCommonLetter
-CharNo
;
89 // Emit code to break out if the prefix doesn't match.
91 // Do the comparison with if (Str[1] != 'f')
92 // FIXME: Need to escape general characters.
93 OS
<< Indent
<< "if (" << StrVariableName
<< "[" << CharNo
<< "] != '"
94 << Matches
[0]->first
[CharNo
] << "')\n";
95 OS
<< Indent
<< " break;\n";
97 // Do the comparison with if memcmp(Str.data()+1, "foo", 3).
98 // FIXME: Need to escape general strings.
99 OS
<< Indent
<< "if (memcmp(" << StrVariableName
<< ".data()+" << CharNo
100 << ", \"" << Matches
[0]->first
.substr(CharNo
, NumChars
) << "\", "
101 << NumChars
<< ") != 0)\n";
102 OS
<< Indent
<< " break;\n";
105 return EmitStringMatcherForChar(Matches
, FirstNonCommonLetter
, IndentCount
,
109 // Otherwise, we have multiple possible things, emit a switch on the
111 OS
<< Indent
<< "switch (" << StrVariableName
<< "[" << CharNo
<< "]) {\n";
112 OS
<< Indent
<< "default: break;\n";
114 for (std::map
<char, std::vector
<const StringPair
*>>::iterator LI
=
115 MatchesByLetter
.begin(), E
= MatchesByLetter
.end(); LI
!= E
; ++LI
) {
116 // TODO: escape hard stuff (like \n) if we ever care about it.
117 OS
<< Indent
<< "case '" << LI
->first
<< "':\t // "
118 << LI
->second
.size() << " string";
119 if (LI
->second
.size() != 1) OS
<< 's';
120 OS
<< " to match.\n";
121 if (EmitStringMatcherForChar(LI
->second
, CharNo
+ 1, IndentCount
+ 1,
123 OS
<< Indent
<< " break;\n";
126 OS
<< Indent
<< "}\n";
130 /// Emit - Top level entry point.
132 void StringMatcher::Emit(unsigned Indent
, bool IgnoreDuplicates
) const {
133 // If nothing to match, just fall through.
134 if (Matches
.empty()) return;
136 // First level categorization: group strings by length.
137 std::map
<unsigned, std::vector
<const StringPair
*>> MatchesByLength
;
139 for (unsigned i
= 0, e
= Matches
.size(); i
!= e
; ++i
)
140 MatchesByLength
[Matches
[i
].first
.size()].push_back(&Matches
[i
]);
142 // Output a switch statement on length and categorize the elements within each
144 OS
.indent(Indent
*2+2) << "switch (" << StrVariableName
<< ".size()) {\n";
145 OS
.indent(Indent
*2+2) << "default: break;\n";
147 for (std::map
<unsigned, std::vector
<const StringPair
*>>::iterator LI
=
148 MatchesByLength
.begin(), E
= MatchesByLength
.end(); LI
!= E
; ++LI
) {
149 OS
.indent(Indent
*2+2) << "case " << LI
->first
<< ":\t // "
151 << " string" << (LI
->second
.size() == 1 ? "" : "s") << " to match.\n";
152 if (EmitStringMatcherForChar(LI
->second
, 0, Indent
, IgnoreDuplicates
))
153 OS
.indent(Indent
*2+4) << "break;\n";
156 OS
.indent(Indent
*2+2) << "}\n";