LCOV - code coverage report
Current view: top level - lib/TableGen - StringMatcher.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 56 56 100.0 %
Date: 2017-09-14 15:23:50 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- StringMatcher.cpp - Generate a matcher for input strings -----------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the StringMatcher class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/TableGen/StringMatcher.h"
      15             : #include "llvm/ADT/StringRef.h"
      16             : #include "llvm/Support/raw_ostream.h"
      17             : #include <cassert>
      18             : #include <map>
      19             : #include <string>
      20             : #include <utility>
      21             : #include <vector>
      22             : 
      23             : using namespace llvm;
      24             : 
      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.
      28             : static unsigned 
      29        2868 : FindFirstNonCommonLetter(const std::vector<const
      30             :                               StringMatcher::StringPair*> &Matches) {
      31             :   assert(!Matches.empty());
      32       34014 :   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       63498 :     char Letter = Matches[0]->first[i];
      35             :     
      36      109974 :     for (unsigned str = 0, e = Matches.size(); str != e; ++str)
      37      141237 :       if (Matches[str]->first[i] != Letter)
      38             :         return i;
      39             :   }
      40             :   
      41             :   return Matches[0]->first.size();
      42             : }
      43             : 
      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.
      47             : ///
      48             : /// \return - True if control can leave the emitted code fragment.
      49        7817 : bool StringMatcher::
      50             : EmitStringMatcherForChar(const std::vector<const StringPair*> &Matches,
      51             :                          unsigned CharNo, unsigned IndentCount) const {
      52             :   assert(!Matches.empty() && "Must have at least one string to match!");
      53       31268 :   std::string Indent(IndentCount*2+4, ' ');
      54             :   
      55             :   // If we have verified that the entire string matches, we're done: output the
      56             :   // matching code.
      57        7817 :   if (CharNo == Matches[0]->first.size()) {
      58             :     assert(Matches.size() == 1 && "Had duplicate keys to match on");
      59             :     
      60             :     // If the to-execute code has \n's in it, indent each subsequent line.
      61        7000 :     StringRef Code = Matches[0]->second;
      62             :     
      63        3500 :     std::pair<StringRef, StringRef> Split = Code.split('\n');
      64       10500 :     OS << Indent << Split.first << "\t // \"" << Matches[0]->first << "\"\n";
      65             : 
      66        3500 :     Code = Split.second;
      67        6382 :     while (!Code.empty()) {
      68        2882 :       Split = Code.split('\n');
      69        2882 :       OS << Indent << Split.first << "\n";
      70        1441 :       Code = Split.second;
      71             :     }
      72             :     return false;
      73             :   }
      74             :   
      75             :   // Bucket the matches by the character we are comparing.
      76        4317 :   std::map<char, std::vector<const StringPair*>> MatchesByLetter;
      77             :   
      78       24122 :   for (unsigned i = 0, e = Matches.size(); i != e; ++i)
      79       61952 :     MatchesByLetter[Matches[i]->first[CharNo]].push_back(Matches[i]);
      80             :   
      81             :   
      82             :   // If we have exactly one bucket to match, see how many characters are common
      83             :   // across the whole set and match all of them at once.
      84        4317 :   if (MatchesByLetter.size() == 1) {
      85        2868 :     unsigned FirstNonCommonLetter = FindFirstNonCommonLetter(Matches);
      86        2868 :     unsigned NumChars = FirstNonCommonLetter-CharNo;
      87             :     
      88             :     // Emit code to break out if the prefix doesn't match.
      89        2868 :     if (NumChars == 1) {
      90             :       // Do the comparison with if (Str[1] != 'f')
      91             :       // FIXME: Need to escape general characters.
      92        1272 :       OS << Indent << "if (" << StrVariableName << "[" << CharNo << "] != '"
      93        1272 :       << Matches[0]->first[CharNo] << "')\n";
      94         848 :       OS << Indent << "  break;\n";
      95             :     } else {
      96             :       // Do the comparison with if memcmp(Str.data()+1, "foo", 3).
      97             :       // FIXME: Need to escape general strings.
      98        7332 :       OS << Indent << "if (memcmp(" << StrVariableName << ".data()+" << CharNo
      99        7332 :          << ", \"" << Matches[0]->first.substr(CharNo, NumChars) << "\", "
     100        2444 :          << NumChars << ") != 0)\n";
     101        4888 :       OS << Indent << "  break;\n";
     102             :     }
     103             :     
     104        2868 :     return EmitStringMatcherForChar(Matches, FirstNonCommonLetter, IndentCount);
     105             :   }
     106             :   
     107             :   // Otherwise, we have multiple possible things, emit a switch on the
     108             :   // character.
     109        4347 :   OS << Indent << "switch (" << StrVariableName << "[" << CharNo << "]) {\n";
     110        2898 :   OS << Indent << "default: break;\n";
     111             :   
     112             :   for (std::map<char, std::vector<const StringPair*>>::iterator LI = 
     113        2898 :        MatchesByLetter.begin(), E = MatchesByLetter.end(); LI != E; ++LI) {
     114             :     // TODO: escape hard stuff (like \n) if we ever care about it.
     115       18620 :     OS << Indent << "case '" << LI->first << "':\t // "
     116        9310 :        << LI->second.size() << " string";
     117        9310 :     if (LI->second.size() != 1) OS << 's';
     118        4655 :     OS << " to match.\n";
     119        9310 :     if (EmitStringMatcherForChar(LI->second, CharNo+1, IndentCount+1))
     120        2446 :       OS << Indent << "  break;\n";
     121             :   }
     122             :   
     123        2898 :   OS << Indent << "}\n";
     124        1449 :   return true;
     125             : }
     126             : 
     127             : /// Emit - Top level entry point.
     128             : ///
     129          43 : void StringMatcher::Emit(unsigned Indent) const {
     130             :   // If nothing to match, just fall through.
     131          88 :   if (Matches.empty()) return;
     132             :   
     133             :   // First level categorization: group strings by length.
     134          82 :   std::map<unsigned, std::vector<const StringPair*>> MatchesByLength;
     135             :   
     136        3582 :   for (unsigned i = 0, e = Matches.size(); i != e; ++i)
     137       14000 :     MatchesByLength[Matches[i].first.size()].push_back(&Matches[i]);
     138             :   
     139             :   // Output a switch statement on length and categorize the elements within each
     140             :   // bin.
     141          41 :   OS.indent(Indent*2+2) << "switch (" << StrVariableName << ".size()) {\n";
     142          41 :   OS.indent(Indent*2+2) << "default: break;\n";
     143             :   
     144             :   for (std::map<unsigned, std::vector<const StringPair*>>::iterator LI =
     145          82 :        MatchesByLength.begin(), E = MatchesByLength.end(); LI != E; ++LI) {
     146         882 :     OS.indent(Indent*2+2) << "case " << LI->first << ":\t // "
     147         588 :        << LI->second.size()
     148         882 :        << " string" << (LI->second.size() == 1 ? "" : "s") << " to match.\n";
     149         294 :     if (EmitStringMatcherForChar(LI->second, 0, Indent))
     150         226 :       OS.indent(Indent*2+4) << "break;\n";
     151             :   }
     152             :   
     153          41 :   OS.indent(Indent*2+2) << "}\n";
     154             : }

Generated by: LCOV version 1.13