FileCheck Enhancement - pattern templates.

[eklepilkina]

Summary

This patch adds opportunity to describe some patterns as named template with or without parameters by using new directive CHECK-PATTERN.

[eklepilkina]

I'll glad if there will be some suggestions how make syntax better. The main idea of this syntax was to use characters with \ for avoiding escaping these characters in standart patterns.

[vsk]

This looks very useful!

My first round of comments do not really address the correctness of this patch (although I do think I found one correctness issue). Please clang-format the diff and upload a diff with more context (e.g git diff -U1000 ...). I can take a closer look once these issues are fixed up :).

test/FileCheck/check-pattern.txt

11

What are the exact semantics of "\:", "\#", and "\=" in the CHECK-PATTERN and CHECK contexts? Please document this and add the documentation to this patch.

I think I have "\#" figured out, but "\:" is confusing (does it make a captured word available via the specified label?). I can't really work out exactly what "\=" is doing -- I'd rather have a spec before picking through the patch :).

12

Could you add a test that shows this behaves properly when different prefixes are in use? E.g;

// RUN: FileCheck -input-file %s %s -check-prefix=FOO
// RUN: FileCheck -input-file %s %s -check-prefix=BAR

// FOO-PATTERN thing: foo-thing
// BAR-PATTERN thing: bar-thing

foo-thing
bar-thing

// FOO: {{\:(thing)}}
// BAR: {{\:(thing)}}

utils/FileCheck/FileCheck.cpp

136

Needs a doxygen comment.

220

I suggest calling this "getNumParameters", and dropping the redundant "\return" doxygen line.

241

Typo, "Parameter". The same typo occurs elsewhere in the diff.

247

Use emplace.

255

Return a StringRef or a const std::string &.

260

Use llvm::SmallSet.

261

I think braces around single-statement loops are usually dropped.

286

Instead of repeatedly re-writing Regex, I suggest creating a SmallVector of expression components and then doing llvm::join(Components).

290

This looks like you're setting yourself up for a use-after-free. This should return a std::string.

295

Avoid static class members.

311

Avoid globals. Also, use a llvm::StringMap<PatternTemplate*> here.

326

NULL is discouraged, use nullptr.

Also, this does 2 table lookups but only needs to do one. E.g something like;

const auto PatternIT = Templates.find(TemplateName);
if (PatternIT == Templates.end())
  return nullptr;
return *PatternIT;

823

Could you elaborate?

[eklepilkina]

test/FileCheck/check-pattern.txt

12

Thank you for this test! There was no problem with prefixes, but was problem with fixed strings instead of patterns. I fixed it.

[eklepilkina]

utils/FileCheck/FileCheck.cpp

823

This means that there may be used described before template as variable.

[aprantl]

docs/CommandGuide/FileCheck.rst

494 ↗

(On Diff #64480)

The CHECK-PATTERN directive is only mentioned in examples but never defined properly.

542 ↗

(On Diff #64480)

The new syntax should be introduced before the examples. This makes it easier to look up the syntax when you use the document as a reference.

[aprantl]

A couple of general remarks about the proposed syntax:

Using CHECK-lines to define meta-variables without checking anything diverges from FileCheck's usual behavior. I find the name CHECK-PATTERN (I know that CHECK can be renamed, but still) particularly misleading and confusing. I would expect something more like CHECK-DEFINE-PATTERN or even passing the patterns to FileCheck on the command line instead.

The syntax of \#, #:, \= is different from what we usually have in FileCheck where we usually use double-brackets "[[" to escape. Why is it so different? Is this borrowed from some other language that users can be expected to have some familiarity with?

docs/CommandGuide/FileCheck.rst

529 ↗

(On Diff #64480)

I don't understand this example. Is it really equivalent to the next example as claimed in the text, or does it have side-effects? If so, what are the side-effects?

[vsk]

More mostly surface-level comments. I think Adrian and I both have concerns over the syntax, so I'll wait a bit before diving into the code.

docs/CommandGuide/FileCheck.rst

522 ↗

(On Diff #64480)

mane -> many

529 ↗

(On Diff #64480)

Is the extra space in \#( reg_hex_num) necessary? I don't want to be too picky / focused on minutiae, but I think this could legitimately be a point of confusion.

529 ↗

(On Diff #64480)

Have you considered changing the syntax for parameter substitution? IMO \:(regName)\=(reg) has two problems: (1) it uses two separate syntactic constructs to do one thing, and (2) it overloads \:, making its meaning context-dependent. I suggest something like this: \=(regName:reg).

540 ↗

(On Diff #64480)

Specify whether or not this can occur in a CHECK-PATTERN line.

test/FileCheck/check-pattern-prefixes.txt

3 ↗

(On Diff #64480)

Check for conflicting parameter definitions:

// RUN: not FileCheck -input-file %s %s -check-prefixes=FOO,BAR

utils/FileCheck/FileCheck.cpp

137

Should return a StringRef. If the caller needs a mutable copy, it can then do: getRegExStr().str().

140

Ditto, return a StringRef (avoids a copy).

194

Since there is only one in-out parameter here, I think the API would be clearer as:

Expected<std::string> ReplaceTemplates(StringRef Str, SourceMgr &SM) (see llvm/Support/Error.h)

203

Use llvm/ADT/IndexedMap.h.

206

StringRef Name

220

Could you drop the \return doxygen line here? I don't think it adds very much.

246

Can drop StringReg(...) if getRegExStr() returns a StringRef.

307

Use std::unique_ptr<PatternTemplate>.

315

Can you find a way to instantiate a TemplatesCollection earlier, and to then pass it by reference into methods/classes which need it? I don't think a singleton approach is much better than having a global.

321

StringRef's are by nature already references. There's no need to pass them by-reference, just copy them.

1015

Use llvm::make_unique<PatternTemplate>.

[eklepilkina]

In D22403#488644, @aprantl wrote:

Using CHECK-lines to define meta-variables without checking anything diverges from FileCheck's usual behavior.

Execuse me, but I didn't understand what do you mean. FileCheck variables are defined in check strings too. And about "without checking": there is checking of earlier definition of this pattern. What do you want to check more?

I would expect something more like CHECK-DEFINE-PATTERN

There is no problem to rename.

or even passing the patterns to FileCheck on the command line instead.

There may be a lot of patterns. Do you mean passing file with patterns?

The syntax of \#, #:, \= is different from what we usually have in FileCheck where we usually use double-brackets "[[" to escape. Why is it so different? Is this borrowed from some other language that users can be expected to have some familiarity with?

This syntax was based on simple regular expressions where \ is escaping character. Syntax is a difficult question. Do you suggest using something like #pattern_name, [[:variable_name]], [[=variable_value]]?
I don't know how users will be better so I would like to know more opinions.

[eklepilkina]

docs/CommandGuide/FileCheck.rst

529 ↗

(On Diff #64480)

Ok. I'll change syntax when there is one decision, because there are more suggestions about changing it.

utils/FileCheck/FileCheck.cpp

203

"The index map template takes two types. The first is the mapped type and the second is a functor that maps its argument to a size_t.".
I need to remember variable position in string. As I uderstood functor should have constructor without parameters, but if I write functor it should have field with position. I can't define position using only parameter name.

[eklepilkina]

docs/CommandGuide/FileCheck.rst

529 ↗

(On Diff #64480)

There was extra space. Without it, test is equivalen.

test/FileCheck/check-pattern-prefixes.txt

3 ↗

(On Diff #64480)

Why should it fail? There will be warning that template with same name exists. And pattern will be assosiated with foo-thing.

utils/FileCheck/FileCheck.cpp

315

If I do so a lot of functions will get one more parameter although many functions will only pass this parameter further. Most of these functions get quite big number of parameters now.

[eklepilkina]

About syntax.
There is an idea to do as you advised.
Suggested new syntax:
[['#template_name]] - use of template 'template_name'. It can occur in CHECK-PATTERN line, when description of one template includes other templates described before. (Without quote, I don't know how escape # here)
[[:Variable_name]] - template variable with name 'variable_name'
[[:variable_name=value]] - current value of template variable(it's needed when you use template with variables).
Is this syntax better? Should I do such way?

[aprantl]

In D22403#489690, @eklepilkina wrote:

About syntax.
There is an idea to do as you advised.
Suggested new syntax:
[['#template_name]] - use of template 'template_name'. It can occur in CHECK-PATTERN line, when description of one template includes other templates described before. (Without quote, I don't know how escape # here)
[[:Variable_name]] - template variable with name 'variable_name'
[[:variable_name=value]] - current value of template variable(it's needed when you use template with variables).
Is this syntax better? Should I do such way?

Let me start off by saying thanks for working on this!

For reference, here is what I remember the syntax of FileCheck CHECK-lines to be currently:

ACTION <- CHECK ':' MATCH '\n' ;
MATCH <- ;
MATCH <- TEXT MATCH ;
MATCH <- REGEX MATCH ;
MATCH <- VAR MATCH ;
REGEX <- '{{' POSIX_REGEX '}}' ;
VAR <- '[[' IDENT ':' POSIX_REGEX ']]' ;
VAR <- '[[' IDENT ']]' ;

Is there a benefit in (or need for) distinguishing between variable uses and pattern uses, or could we piggyback the existing syntax?

As for pattern variables, I really think this review would benefit if we could split out pattern variables into a separate review. I didn't yet understand how pattern variables are supposed to work: Is \:(variable)\=(value) supposed to be an argument to a pattern use that immediately precedes it? Or is it modifying global state similar to regular variable definition in FileCheck? If the latter is the case, why does it come after the pattern in the example? In the former case, wouldn't it be better to have syntax that looks more like passing in an argument?

[eklepilkina]

In D22403#489895, @aprantl wrote:

Is there a benefit in (or need for) distinguishing between variable uses and pattern uses, or could we piggyback the existing syntax?

There is difference between patterns and variables so we should understand where variable is, where pattern is.

As for pattern variables, I really think this review would benefit if we could split out pattern variables into a separate review. I didn't yet understand how pattern variables are supposed to work: Is \:(variable)\=(value) supposed to be an argument to a pattern use that immediately precedes it? Or is it modifying global state similar to regular variable definition in FileCheck? If the latter is the case, why does it come after the pattern in the example? In the former case, wouldn't it be better to have syntax that looks more like passing in an argument?

I a bit misuderstand how can I split out pattern variables into a separate review, because this review need all these changes. We can't use pattern variable without patterns, so separate review will duplicate part of changes of pattern review.
Pattren variables supposed to help create one pattern when you have a lot of similar checks.
For example

CHECK-DEFINE-PATTERN reg: {{\:(RegName)0x[0-9a-fA-F]+}}

This is pattern for defining register, and name is parameter. Template is saved in such way.
Then you can use it.
CHECK: {{\#(reg)\:(RegName)\=(REG)}}
When you write such check, FileCheck will replace it with template where variable name is changed to it's value. Variable name is some kind of named spaceholder.
The previous check-line will be equivalent to
CHECK: {{REG0x[0-9a-fA-F]+}}
We should have difference between pattern variable and global variables because we can use global variable in pattern or as value of pattern variable.

[aprantl]

In D22403#490814, @eklepilkina wrote:

In D22403#489895, @aprantl wrote:

Is there a benefit in (or need for) distinguishing between variable uses and pattern uses, or could we piggyback the existing syntax?

There is difference between patterns and variables so we should understand where variable is, where pattern is.

They are also both placeholders for a pattern. Can you give an example where it is useful to tell the difference between a use of a pattern and a use of a plain old variable? Does it make the test more readable?
I'm not saying that we have to share the syntax, but adding more syntax increases the cognitive load on testcase authors and we should make sure we are doing it for the right reasons.

As for pattern variables, I really think this review would benefit if we could split out pattern variables into a separate review.

I a bit misuderstand how can I split out pattern variables into a separate review, because this review need all these changes.

If you feel like splitting out the pattern variables into a separate review ins't feasible that's fine with me.

Could you please answer the following questions specifically?

I didn't yet understand how pattern variables are supposed to work: Is \:(variable)\=(value) supposed to be an argument to a pattern use that immediately precedes it? Or is it modifying global state similar to regular variable definition in FileCheck? If the latter is the case, why does it come after the pattern in the example? In the former case, wouldn't it be better to have syntax that looks more like passing in an argument?

Pattren variables supposed to help create one pattern when you have a lot of similar checks.
For example

CHECK-DEFINE-PATTERN reg: {{\:(RegName)0x[0-9a-fA-F]+}}

This is pattern for defining register, and name is parameter. Template is saved in such way.
Then you can use it.
// CHECK: {{\#(reg)\:(RegName)\=(REG)}}
When you write such check, FileCheck will replace it with template where variable name is changed to it's value. Variable name is some kind of named spaceholder.

In the documentation the example showed a pattern use on its own, here it appears inside of a regexp. To make sure I understand the proposal correctly :-) it might help if you could add your new syntax to the grammar I posted earlier.

thanks!
adrian

[eklepilkina]

In D22403#491468, @aprantl wrote:

They are also both placeholders for a pattern. Can you give an example where it is useful to tell the difference between a use of a pattern and a use of a plain old variable? Does it make the test more readable?
I'm not saying that we have to share the syntax, but adding more syntax increases the cognitive load on testcase authors and we should make sure we are doing it for the right reasons.

Firstly, variables should be defined in some check-line. So we can't create variables separately. In case of patterns you can create a lot of frequently used patterns once (for example in separate file and then include this file where you need (see patch https://reviews.llvm.org/D22500)). Moreover pattern can have their own variables.

I didn't yet understand how pattern variables are supposed to work: Is \:(variable)\=(value) supposed to be an argument to a pattern use that immediately precedes it? Or is it modifying global state similar to regular variable definition in FileCheck?

Variables are arguments. I don't understand what the global state do you mean.

If the latter is the case, why does it come after the pattern in the example? In the former case, wouldn't it be better to have syntax that looks more like passing in an argument?

Do you mean something like \#pattern(a, b)? Or what? There is no order of variables during defining it. One variable can be used in pattern several times in different places. I just need variable name to find place in pattern and its value.

In the documentation the example showed a pattern use on its own, here it appears inside of a regexp. To make sure I understand the proposal correctly :-)

Yes, I have a mistake in documentation. Now pattern can be used only in regular expressions. But if we change syntax to use [[ ]], I'll can add possible use of them in fixed strings in line-checks.

it might help if you could add your new syntax to the grammar I posted earlier.

Syntax as is now.

ACTION <- CHECK-DEFINE-PATTERN IDENT ':' MATCH '\n' ;
ACTION <- CHECK-DEFINE-PATTERN IDENT ':' REGEX_DEF '\n' ;
PATTERN_VAR <-;
PATTERN_VAR <-' \:('IDENT')';
REGEX_VARS <- POSIX_REGEX;
REGEX_VARS <- REGEX_VARS PATTERN_VAR REGEX_VARS;
REGEX_DEF <- '{{' REGEX_VARS '}}';
VAR_VALUE <-;
VAR_VALUE <- '\:('IDENT')\=('TEXT')' VAR_VALUE;
PATTERN_USE <- POSIX_REGEX;
PATTERN_USE <- POSIX_REGEX '\#('IDENT')'VAR_VALUE PATTERN_USE;
REGEX <- '{{' PATTERN_USE '}}';

[eklepilkina]

Change syntax to new one suggested by Vedant Kumar.

ACTION <- CHECK ':' MATCH '\n' ;

ACTION <- CHECK-DEFINE-PATTERN ':' IDENT PARAMLIST? ':' PATTERN_ELEMENT* '\n' ;
PARAMLIST <- '(' IDENT (',' IDENT)* ')' ;
PATTERN_ELEMENT <- IDENT | REGEX;
MATCH <- (TEXT | REGEX | PATTERN_USE | VAR)* ;
REGEX <- '{{' POSIX_REGEX '}}' ;
PATTERN_USE <- '[[' '@' IDENT  ARGLIST? ']]' ;
VAR <- '[[' IDENT ':' POSIX_REGEX ']]' ;
VAR <- '[[' IDENT '@' IDENT ARGLIST? ']]' ;
ARGLIST <- '(' ARG (',' ARG)* ')' ;
ARG <- "([^"]|\\")*" ;

[vsk]

I've added a few comments inline which I hope will be useful. However, after looking this patch over a few times, I've found that it's too large for me to review constructively.

The main issue is that the grammar you've implemented doesn't correspond to the one we discussed. E.g your PATTERN_ELEMENT includes PATTERN_USE, and your ARG is not handled correctly. I don't want to say "no" to new features, but I would much rather have them land incrementally, with more testing for edge-cases and more documentation. Can you scale back this patch to just cover these new bits of the grammar?

ACTION <- CHECK-DEFINE-PATTERN ':' IDENT ':' PATTERN_ELEMENT* '\n' ;
PATTERN_ELEMENT <- IDENT | REGEX;
MATCH <- PATTERN_USE ;
PATTERN_USE <- '[[' '@' IDENT ']]' ;
VAR <- '[[' IDENT '@' IDENT ']]' ;

docs/CommandGuide/FileCheck.rst

488 ↗

(On Diff #70696)

Please use the same formatting rules as the rest of this document. Can you trim the twiddles ("~~~") to match the section name's length and line-wrap text that isn't in a code block?

495 ↗

(On Diff #70696)

Please summarize the new syntax in the paragraph above, and use small examples here instead.

test/FileCheck/check-pattern.txt

25

Add tests for:

1. All error messages you've introduced
2. Allow -check-prefix=FOO, FOO-DEFINE-PATTERN
3. Disallow BAR-DEFINE-PATTERN and FOO-DEFINE-PATTERN for the same definition name
4. Capture '@LINE' in a variable
5. Disallow using a pattern captured with a FOO-definition in a BAR check
6. Verify CHECK-{NEXT, SAME, DAG} etc. work with captured patterns

[eklepilkina]

Are quotes necessary for parameters? Everything is string in FileCheck.
Using patterns and variables was in old grammer. I thought that we only change syntax, so I added this feature too.
Ok, I'll remove this from this patch. But then I want to add using patterns and variables in definitions later. On my opinion these features are quite useful.

[vsk]

In D22403#539395, @eklepilkina wrote:

Are quotes necessary for parameters? Everything is string in FileCheck.

Yes, the quotes are necessary. Without them the grammar is ambiguous. Consider the string '@foo(a, b)'. Is there just one argument to foo (the string "a, b"), or are there two arguments ("a" and "b")?

Using patterns and variables was in old grammer. I thought that we only change syntax, so I added this feature too.
Ok, I'll remove this from this patch. But then I want to add using patterns and variables in definitions later. On my opinion these features are quite useful.

Sounds great :).

[eklepilkina]

test/FileCheck/check-pattern.txt

25

Capture '@LINE' in a variable

I don't understand what do you mean. How can I do this? CHECK: [[Number: [[@LINE]]]]?
Or do you mean text '@LINE'?

[eklepilkina]

Patch without modifiers for pattern parameters and using pattern and variables inside definition of other patterns.

[alexfh]

IIUC, there was no consensus about usefulness of this change.

test/FileCheck/check-pattern.txt

+// RUN: FileCheck -input-file %s %s
+
+op0xA1;
+op0xc2;
+op0x33;
+// CHECK-PATTERN hex_num: {{0x[0-9a-fA-F]+}}
+// CHECK-PATTERN reg: {{\:(RegName)\#(hex_num)}}
+// CHECK-PATTERN operation: {{\:(OpName) \#(reg)\:(RegName)\=(r), \#(reg)\:(RegName)\=(reg)}}
+// CHECK-PATTERN inc: {{\:(VarName) = \:(VarName)\+\:(Number)}}
+// CHECK-PATTERN alt: {{x|y}}
+// CHECK-PATTERN altincheck: check {{\#(alt)}}
+
+// CHECK: {{op\#(hex_num)}};
+reg0x0
+// CHECK: {{\#(reg)\:(RegName)\=(reg)}}
+
+ADD r0xA, reg0x10
+// CHECK: {{\#(operation)\:(OpName)\=(ADD)}}
+
+TEMP = TEMP+4
+// CHECK: {{\#(inc)\:(Number)\=(4)\:(VarName)\=(TEMP)}}
+
+check y
+// CHECK: {{\#altincheck}}

utils/FileCheck/FileCheck.cpp

 #include <string>
 #include <system_error>
 #include <vector>
+#include <set>
 using namespace llvm;
 
 static cl::opt<std::string>

     CheckNot,
     CheckDAG,
     CheckLabel,
+    CheckPattern,
 
     /// MatchEOF - When set, this pattern only matches the end of file. This is
     /// used for trailing CHECK-NOTs.

   /// getLoc - Return the location in source code.
   SMLoc getLoc() const { return PatternLoc; }
 
+  std::string getRegExStr() const { return RegExStr; }
+
   /// ParsePattern - Parse the given string into the Pattern. Prefix provides
   /// which prefix is being matched, SM provides the SourceMgr used for error
   /// reports, and LineNumber is the line number in the input file from which

   /// \return offset of the closing sequence within Str, or npos if it was not
   /// found.
   size_t FindRegexVarEnd(StringRef Str, SourceMgr &SM);
+
+  /// Replace templates if they are to associated with them regular expressions.
+  /// \return true if there is error in regular expression
+  bool ReplaceTemplates(StringRef RS, SourceMgr &SM, std::string &ResultRegex);
+};
+
+class PatternTemplate {
+  /// Name of template.
+  std::string TemplateName;
+  /// Pattern which describes this template.
+  Pattern TemplatePattern;
+  /// Template parametrs.
+  std::map<size_t, StringRef> Parameters;
+
+public:
+  PatternTemplate(std::string Name, Check::CheckType Ty = Check::CheckType::CheckNone): 
+          TemplateName(Name), TemplatePattern(Pattern(Ty)) {}
+
+  PatternTemplate(Check::CheckType Ty = Check::CheckType::CheckNone):TemplatePattern(Pattern(Ty)) {}
+
+  /// Parse the given string for getting parameters of template.
+  /// \return true if string has error in description regular expression or parametrs.
+  bool ParseTemplate(StringRef TemplateString,
+                     StringRef Prefix,
+                     SourceMgr &SM,
+                     unsigned LineNumber);
+
+  /// Get template name.
+  /// \return template name.
+  std::string GetTemplateName() const;
+
+  /// Get number of parametrs which this template includes.
+  /// \return parameters number.
+  size_t GetParametersNumber() const;
+
+  /// Checks if this template has such parameter
+  /// \return true if template has.
+  bool HasParameter(StringRef ParameterName) const;
+
+  /// Generate result regular expression for matching with inserted parameters values.
+  StringRef GetRegularExpression(std::map<StringRef, StringRef> &ParametersValues) const;
 };
 
 
+bool PatternTemplate::ParseTemplate(StringRef TemplateString,
+                             StringRef Prefix,
+                             SourceMgr &SM,
+                             unsigned LineNumber) {
+
+  if (TemplatePattern.ParsePattern(TemplateString, Prefix, SM, LineNumber))
+    return true;
+
+  // Find parametrs in pattern
+  SmallVector<StringRef, 2> Matches;
+  Regex Parametr(StringRef("\\\\:\\(([a-zA-Z_0-9]+)\\)"));
+  size_t DiffInLoc = 0;
+  StringRef PatternString = StringRef(TemplatePattern.getRegExStr());
+
+  while (Parametr.match(PatternString, &Matches)) {
+    size_t ParametrPos = Matches[0].data() - PatternString.data();
+    Parameters.insert(std::pair<size_t, StringRef>(ParametrPos + DiffInLoc, Matches[1]));
+    PatternString = PatternString.drop_front(ParametrPos + Matches[1].size() + 3);
+    DiffInLoc += ParametrPos + Matches[1].size() + 3;
+  }
+
+  return false;
+}
+
+std::string PatternTemplate::GetTemplateName() const {
+  return TemplateName;
+}
+
+size_t PatternTemplate::GetParametersNumber() const {
+  std::set<StringRef> UniqueParametrs;
+  for (const auto &Parameter : Parameters) {
+    UniqueParametrs.insert(Parameter.second);
+  }
+  return UniqueParametrs.size();
+}
+  
+bool PatternTemplate::HasParameter(StringRef ParameterName) const {
+  for (const auto &Parameter : Parameters) {
+    if (Parameter.second == ParameterName) {
+      return true;
+    }
+  }
+  return false;
+}
+
+StringRef PatternTemplate::GetRegularExpression(std::map<StringRef, StringRef> &ParametersValues) const {
+  std::string Regex = TemplatePattern.getRegExStr();
+
+  int DiffInLoc = 0;  // variable for shifts after replacing parametrs' names by parametrs' values
+
+  // Change all parameters to their values.
+  for (const auto &Parameter : Parameters) {
+    StringRef Value = ParametersValues[Parameter.second];
+    std::string RegexStart = StringRef(Regex.substr(0, Parameter.first + DiffInLoc)).str();
+    StringRef RegexEnd = Regex.substr(Parameter.first + DiffInLoc + Parameter.second.size() + 4);
+    Regex = RegexStart + "(" + Value.str() + ")" + RegexEnd.str();
+    DiffInLoc += Value.size() - Parameter.second.size() - 2;
+  }
+
+  return StringRef(Regex);
+}
+
+class TemplatesCollection {
+  /// Described templates
+  static std::map<std::string, PatternTemplate*> Templates;
+  /// Last added template (for generating error)
+  static std::string LastAddedTemplate;
+
+public:
+  /// Add template
+  static bool AddTemplate(PatternTemplate *AddedTemplate);
+  /// Get template by its name.
+  static PatternTemplate* GetTemplate(const StringRef &TemplateName);
+  /// Get last added template
+  static PatternTemplate* GetLastAddedTemplate();
+  /// Check if there is current template in collection.
+  static bool HasTemplate(const StringRef &TemplateName);
+};
+
+std::string TemplatesCollection::LastAddedTemplate;
+std::map<std::string, PatternTemplate*> TemplatesCollection::Templates;
+
+bool TemplatesCollection::AddTemplate(PatternTemplate *AddedTemplate) {
+  if (Templates.find(AddedTemplate->GetTemplateName()) != Templates.end()) {
+    return false;
+  }
+  LastAddedTemplate = AddedTemplate->GetTemplateName();
+  return Templates.insert(std::pair<std::string, PatternTemplate*>(AddedTemplate->GetTemplateName(), AddedTemplate)).second;
+}
+
+PatternTemplate* TemplatesCollection::GetTemplate(const StringRef &TemplateName) {
+  if (HasTemplate(TemplateName)) {
+    return Templates[TemplateName.str()];
+  }
+
+  return NULL;
+}
+
+PatternTemplate* TemplatesCollection::GetLastAddedTemplate() {
+  return Templates[LastAddedTemplate];
+}
+
+bool TemplatesCollection::HasTemplate(const StringRef &TemplateName) {
+  return Templates.find(TemplateName.str()) != Templates.end();
+}
+
+
 bool Pattern::ParsePattern(StringRef PatternStr,
                            StringRef Prefix,
                            SourceMgr &SM,

 
 bool Pattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen,
                               SourceMgr &SM) {
+  std::string ResultRegex;
+  if (ReplaceTemplates(RS, SM, ResultRegex))
+    return true;
+  
+  RS = StringRef(ResultRegex);
   Regex R(RS);
   std::string Error;
   if (!R.isValid(Error)) {

   return StringRef::npos;
 }
 
+bool Pattern::ReplaceTemplates(StringRef RS, SourceMgr &SM, std::string &ResultRegex) {
+  // Replace templates with regular expressions.
+  SmallVector<StringRef, 2> MatchInfo;
+  size_t DiffInLoc = 0;
+  StringRef RegexStr = StringRef(RS);
+
+  while (Regex(StringRef("\\\\#\\(([a-zA-Z0-9_]+)\\)")).match(RegexStr, &MatchInfo)) {
+
+    // Check if template was declared
+    if (!TemplatesCollection::HasTemplate(MatchInfo[1])) {
+      SM.PrintMessage(SMLoc::getFromPointer(RS.data() + DiffInLoc + (MatchInfo[1].data() - RegexStr.data())), SourceMgr::DK_Error,
+                    "template " + MatchInfo[1].str() + " wasn't declared");
+      return true;
+    }
+    // Add pat of regex before template usage.
+    ResultRegex = ResultRegex + RegexStr.substr(0, MatchInfo[0].data() - RegexStr.data()).str();
+    RegexStr = RegexStr.drop_front(MatchInfo[0].data() - RegexStr.data() + MatchInfo[0].size());
+
+    DiffInLoc += MatchInfo[0].data() - RegexStr.data() + MatchInfo[0].size();
+    PatternTemplate *Temp = TemplatesCollection::GetTemplate(MatchInfo[1]);
+
+    // Get template parametres.
+    std::map<StringRef, StringRef> ParametersValues;
+    while (RegexStr.startswith("\\:(")) {
+      size_t ParameterNameEnd = RegexStr.find(')');
+      if (ParameterNameEnd == StringRef::npos) {
+        SM.PrintMessage(SMLoc::getFromPointer(RS.data() + DiffInLoc), SourceMgr::DK_Error,
+                    "wrong description of parameter. No closed bracket.");
+        return true;
+      }
+      StringRef ParameterName = RegexStr.substr(3, ParameterNameEnd - 3);
+
+      // Check if template has such parametr in description.
+      if (!Temp->HasParameter(ParameterName)) {
+        SM.PrintMessage(SMLoc::getFromPointer(RS.data() + DiffInLoc), SourceMgr::DK_Error,
+                    "template " + MatchInfo[1].str() + " doesn't have parameter " + ParameterName.str());
+        return true;
+      }
+
+      // Find value of parameter.
+      DiffInLoc += ParameterNameEnd + 1;
+      RegexStr = RegexStr.drop_front(ParameterNameEnd + 1);
+      if (!RegexStr.startswith("\\=(")) {
+        SM.PrintMessage(SMLoc::getFromPointer(RS.data() + DiffInLoc), SourceMgr::DK_Error,
+                    "parameter " + ParameterName.str() + " has no value");
+        return true;
+      }
+
+      size_t ParameterValueEnd = RegexStr.find(')');
+      if (ParameterValueEnd == StringRef::npos) {
+        SM.PrintMessage(SMLoc::getFromPointer(RS.data() + DiffInLoc), SourceMgr::DK_Error,
+                    "wrong description of parameter value. No closed bracket.");
+        return true;
+      }
+      StringRef ParameterValue = RegexStr.substr(3, ParameterValueEnd - 3);
+
+      // TODO - may value be template?
+      ParametersValues.insert(std::pair<StringRef, StringRef>(ParameterName, ParameterValue));
+
+      DiffInLoc += ParameterValueEnd + 1;
+      RegexStr = RegexStr.drop_front(ParameterValueEnd + 1);
+    }
+
+    if (Temp->GetParametersNumber() != ParametersValues.size()) {
+      SM.PrintMessage(SMLoc::getFromPointer(RS.data() + DiffInLoc), SourceMgr::DK_Error,
+                    "not all parametrs of template " + Temp->GetTemplateName() + " are defined");
+      return true;
+    }
+
+    // Get regular expression by template.
+    StringRef FullTemplateRegex = Temp->GetRegularExpression(ParametersValues);
+    // Add template regex.
+    ResultRegex = ResultRegex + FullTemplateRegex.str();
+
+  }
+  // Add left part without templates.
+  ResultRegex = ResultRegex + RegexStr.str();
+  return false;
+}
+
 
 //===----------------------------------------------------------------------===//
 // Check Strings.

   return (isalnum(c) || c == '-' || c == '_');
 }
 
-// Get the size of the prefix extension.
-static size_t CheckTypeSize(Check::CheckType Ty) {
-  switch (Ty) {
-  case Check::CheckNone:
-  case Check::CheckBadNot:
-    return 0;
-
-  case Check::CheckPlain:
-    return sizeof(":") - 1;
-
-  case Check::CheckNext:
-    return sizeof("-NEXT:") - 1;
-
-  case Check::CheckSame:
-    return sizeof("-SAME:") - 1;
-
-  case Check::CheckNot:
-    return sizeof("-NOT:") - 1;
-
-  case Check::CheckDAG:
-    return sizeof("-DAG:") - 1;
-
-  case Check::CheckLabel:
-    return sizeof("-LABEL:") - 1;
-
-  case Check::CheckEOF:
-    llvm_unreachable("Should not be using EOF size");
-  }
-
-  llvm_unreachable("Bad check type");
-}
-
-static Check::CheckType FindCheckType(StringRef Buffer, StringRef Prefix) {
+static Check::CheckType FindCheckType(SourceMgr &SM, StringRef Buffer, StringRef Prefix, size_t &CheckTypeSize) {
   char NextChar = Buffer[Prefix.size()];
+  CheckTypeSize = 0;
 
   // Verify that the : is present after the prefix.
-  if (NextChar == ':')
+  if (NextChar == ':') {
+    CheckTypeSize = 1;
     return Check::CheckPlain;
+  }
 
   if (NextChar != '-')
     return Check::CheckNone;
 
   StringRef Rest = Buffer.drop_front(Prefix.size() + 1);
-  if (Rest.startswith("NEXT:"))
+  if (Rest.startswith("NEXT:")) {
+    CheckTypeSize = sizeof("-NEXT:") - 1;
     return Check::CheckNext;
+  }
 
-  if (Rest.startswith("SAME:"))
+  if (Rest.startswith("SAME:")) {
+    CheckTypeSize = sizeof("-SAME:") - 1;
     return Check::CheckSame;
+  }
 
-  if (Rest.startswith("NOT:"))
+  if (Rest.startswith("NOT:")) {
+    CheckTypeSize = sizeof("-NOT:") - 1;
     return Check::CheckNot;
+  }
 
-  if (Rest.startswith("DAG:"))
+  if (Rest.startswith("DAG:")) {
+    CheckTypeSize = sizeof("-DAG:") - 1;
     return Check::CheckDAG;
+  }
 
-  if (Rest.startswith("LABEL:"))
+  if (Rest.startswith("LABEL:")) {
+    CheckTypeSize = sizeof("-LABEL:") - 1;
     return Check::CheckLabel;
+  }
+
+  SmallVector<StringRef, 20> Matches;
+
+  if (Regex(StringRef("PATTERN ([a-zA-Z0-9_]+):"), Regex::Newline).match(Rest, &Matches)) {
+    if (!TemplatesCollection::AddTemplate(new PatternTemplate(Matches[1]))) {
+      SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
+                        SourceMgr::DK_Warning,
+                        "the template name " + Matches[1].str() + "is already used");
+      return Check::CheckNone;
+    }
+    CheckTypeSize = Matches[0].size() + 1;
+    return Check::CheckPattern;
+  }
 
   // You can't combine -NOT with another suffix.
   if (Rest.startswith("DAG-NOT:") || Rest.startswith("NOT-DAG:") ||

 // string and the location will be StringRef::npos. If one prefix is a substring
 // of another, the maximal match should be found. e.g. if "A" and "AA" are
 // prefixes then AA-CHECK: should match the second one.
-static StringRef FindFirstCandidateMatch(StringRef &Buffer,
+static StringRef FindFirstCandidateMatch(SourceMgr &SM, StringRef &Buffer,
                                          Check::CheckType &CheckTy,
-                                         size_t &CheckLoc) {
+                                         size_t &CheckLoc, 
+                                         size_t &CheckTypeSize) {
   StringRef FirstPrefix;
   size_t FirstLoc = StringRef::npos;
+  size_t FirstTypeSize = StringRef::npos;
   size_t SearchLoc = StringRef::npos;
   Check::CheckType FirstTy = Check::CheckNone;
 

     if (PrefixLoc != 0 && IsPartOfWord(Buffer[PrefixLoc - 1]))
       FirstTy = Check::CheckNone;
     else
-      FirstTy = FindCheckType(Rest, Prefix);
+      FirstTy = FindCheckType(SM, Rest, Prefix, FirstTypeSize);
 
     FirstLoc = PrefixLoc;
     FirstPrefix = Prefix;

 
   CheckTy = FirstTy;
   CheckLoc = FirstLoc;
+  CheckTypeSize = FirstTypeSize;
   return FirstPrefix;
 }
 
-static StringRef FindFirstMatchingPrefix(StringRef &Buffer,
+static StringRef FindFirstMatchingPrefix(SourceMgr &SM, StringRef &Buffer,
                                          unsigned &LineNumber,
                                          Check::CheckType &CheckTy,
-                                         size_t &CheckLoc) {
+                                         size_t &CheckLoc,
+                                         size_t &CheckTypeSize) {
   while (!Buffer.empty()) {
-    StringRef Prefix = FindFirstCandidateMatch(Buffer, CheckTy, CheckLoc);
+    StringRef Prefix = FindFirstCandidateMatch(SM, Buffer, CheckTy, CheckLoc, CheckTypeSize);
     // If we found a real match, we are done.
     if (!Prefix.empty()) {
       LineNumber += Buffer.substr(0, CheckLoc).count('\n');

   while (1) {
     Check::CheckType CheckTy;
     size_t PrefixLoc;
+    size_t CheckTypeSize;
 
     // See if a prefix occurs in the memory buffer.
-    StringRef UsedPrefix = FindFirstMatchingPrefix(Buffer,
+    StringRef UsedPrefix = FindFirstMatchingPrefix(SM, Buffer,
                                                    LineNumber,
                                                    CheckTy,
-                                                   PrefixLoc);
+                                                   PrefixLoc,
+                                                   CheckTypeSize);
     if (UsedPrefix.empty())
       break;
 

     const char *UsedPrefixStart = Buffer.data() + (PrefixLoc == 0 ? 0 : 1);
 
     // PrefixLoc is to the start of the prefix. Skip to the end.
-    Buffer = Buffer.drop_front(UsedPrefix.size() + CheckTypeSize(CheckTy));
+    Buffer = Buffer.drop_front(UsedPrefix.size() + CheckTypeSize);
 
     // Complain about useful-looking but unsupported suffixes.
     if (CheckTy == Check::CheckBadNot) {

     // Remember the location of the start of the pattern, for diagnostics.
     SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());
 
+    if (CheckTy == Check::CheckType::CheckPattern) {
+      if (TemplatesCollection::GetLastAddedTemplate()->ParseTemplate(Buffer.substr(0, EOL), UsedPrefix, SM, LineNumber)) {
+        return true;
+      }
+      Buffer = Buffer.substr(EOL);
+      continue;
+    }
+
     // Parse the pattern.
     Pattern P(CheckTy);
     if (P.ParsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, LineNumber))