1 // Copyright 2008 The RE2 Authors. All Rights Reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 #ifndef RE2_TESTING_REGEXP_GENERATOR_H_ 6 #define RE2_TESTING_REGEXP_GENERATOR_H_ 7 8 // Regular expression generator: generates all possible 9 // regular expressions within given parameters (see below for details). 10 11 #include <stdint.h> 12 #include <random> 13 #include <string> 14 #include <vector> 15 16 #include "util/util.h" 17 #include "re2/stringpiece.h" 18 19 namespace re2 { 20 21 // Regular expression generator. 22 // 23 // Given a set of atom expressions like "a", "b", or "." 24 // and operators like "%s*", generates all possible regular expressions 25 // using at most maxbases base expressions and maxops operators. 26 // For each such expression re, calls HandleRegexp(re). 27 // 28 // Callers are expected to subclass RegexpGenerator and provide HandleRegexp. 29 // 30 class RegexpGenerator { 31 public: 32 RegexpGenerator(int maxatoms, int maxops, const std::vector<string>& atoms, 33 const std::vector<string>& ops); ~RegexpGenerator()34 virtual ~RegexpGenerator() {} 35 36 // Generates all the regular expressions, calling HandleRegexp(re) for each. 37 void Generate(); 38 39 // Generates n random regular expressions, calling HandleRegexp(re) for each. 40 void GenerateRandom(int32_t seed, int n); 41 42 // Handles a regular expression. Must be provided by subclass. 43 virtual void HandleRegexp(const string& regexp) = 0; 44 45 // The egrep regexp operators: * + ? | and concatenation. 46 static const std::vector<string>& EgrepOps(); 47 48 private: 49 void RunPostfix(const std::vector<string>& post); 50 void GeneratePostfix(std::vector<string>* post, int nstk, int ops, int lits); 51 bool GenerateRandomPostfix(std::vector<string>* post, int nstk, int ops, 52 int lits); 53 54 int maxatoms_; // Maximum number of atoms allowed in expr. 55 int maxops_; // Maximum number of ops allowed in expr. 56 std::vector<string> atoms_; // Possible atoms. 57 std::vector<string> ops_; // Possible ops. 58 std::minstd_rand0 rng_; // Random number generator. 59 60 RegexpGenerator(const RegexpGenerator&) = delete; 61 RegexpGenerator& operator=(const RegexpGenerator&) = delete; 62 }; 63 64 // Helpers for preparing arguments to RegexpGenerator constructor. 65 66 // Returns one string for each character in s. 67 std::vector<string> Explode(const StringPiece& s); 68 69 // Splits string everywhere sep is found, returning 70 // vector of pieces. 71 std::vector<string> Split(const StringPiece& sep, const StringPiece& s); 72 73 } // namespace re2 74 75 #endif // RE2_TESTING_REGEXP_GENERATOR_H_ 76