Introduce BalancedDelimiterTracker, to better track open/close
delimiter pairs and detect when we exceed the implementation limit for
nesting depth, from Aaron Ballman!
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@141782 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/docs/InternalsManual.html b/docs/InternalsManual.html
index 2829dbd..da83d89 100644
--- a/docs/InternalsManual.html
+++ b/docs/InternalsManual.html
@@ -1810,7 +1810,7 @@
<li>Write tests for all of the "bad" parsing cases, to make sure
your recovery is good. If you have matched delimiters (e.g.,
parentheses, square brackets, etc.), use
- <tt>Parser::MatchRHSPunctuation</tt> to give nice diagnostics when
+ <tt>Parser::BalancedDelimiterTracker</tt> to give nice diagnostics when
things go wrong.</li>
</ul>
</li>
diff --git a/include/clang/Basic/DiagnosticParseKinds.td b/include/clang/Basic/DiagnosticParseKinds.td
index 7757306..733eccc 100644
--- a/include/clang/Basic/DiagnosticParseKinds.td
+++ b/include/clang/Basic/DiagnosticParseKinds.td
@@ -354,6 +354,8 @@
"destructor name %0 does not refer to a template">;
def err_default_arg_unparsed : Error<
"unexpected end of default argument expression">;
+def err_parser_impl_limit_overflow : Error<
+ "parser recursion limit reached, program too complex">, DefaultFatal;
// C++ derived classes
def err_dup_virtual : Error<"duplicate 'virtual' in base specifier">;
diff --git a/include/clang/Parse/Parser.h b/include/clang/Parse/Parser.h
index e1e2402..eed8862 100644
--- a/include/clang/Parse/Parser.h
+++ b/include/clang/Parse/Parser.h
@@ -409,6 +409,84 @@
return PP.LookAhead(0);
}
+ /// \brief Tracks information about the current nesting depth of
+ /// opening delimiters of each kind.
+ class DelimiterTracker {
+ private:
+ friend class Parser;
+
+ unsigned Paren, Brace, Square, Less, LLLess;
+ unsigned& get(tok::TokenKind t) {
+ switch (t) {
+ default: llvm_unreachable("Unexpected balanced token");
+ case tok::l_brace: return Brace;
+ case tok::l_paren: return Paren;
+ case tok::l_square: return Square;
+ case tok::less: return Less;
+ case tok::lesslessless: return LLLess;
+ }
+ }
+
+ void push(tok::TokenKind t) {
+ get(t)++;
+ }
+
+ void pop(tok::TokenKind t) {
+ get(t)--;
+ }
+
+ unsigned getDepth(tok::TokenKind t) {
+ return get(t);
+ }
+
+ public:
+ DelimiterTracker() : Paren(0), Brace(0), Square(0), Less(0), LLLess(0) { }
+ };
+
+ /// \brief RAII class that helps handle the parsing of an open/close delimiter
+ /// pair, such as braces { ... } or parentheses ( ... ).
+ class BalancedDelimiterTracker {
+ tok::TokenKind Kind, Close;
+ Parser& P;
+ bool Cleanup;
+ const unsigned MaxDepth;
+ SourceLocation LOpen, LClose;
+
+ void assignClosingDelimiter() {
+ switch (Kind) {
+ default: llvm_unreachable("Unexpected balanced token");
+ case tok::l_brace: Close = tok::r_brace; break;
+ case tok::l_paren: Close = tok::r_paren; break;
+ case tok::l_square: Close = tok::r_square; break;
+ case tok::less: Close = tok::greater; break;
+ case tok::lesslessless: Close = tok::greatergreatergreater; break;
+ }
+ }
+
+ public:
+ BalancedDelimiterTracker(Parser& p, tok::TokenKind k)
+ : Kind(k), P(p), Cleanup(false), MaxDepth(256) {
+ assignClosingDelimiter();
+ }
+
+ ~BalancedDelimiterTracker() {
+ if (Cleanup)
+ P.QuantityTracker.pop(Kind);
+ }
+
+ SourceLocation getOpenLocation() const { return LOpen; }
+ SourceLocation getCloseLocation() const { return LClose; }
+ SourceRange getRange() const { return SourceRange(LOpen, LClose); }
+
+ bool consumeOpen();
+ bool expectAndConsume(unsigned DiagID,
+ const char *Msg = "",
+ tok::TokenKind SkipToTok = tok::unknown);
+ bool consumeClose();
+ };
+
+ DelimiterTracker QuantityTracker;
+
/// getTypeAnnotation - Read a parsed type out of an annotation token.
static ParsedType getTypeAnnotation(Token &Tok) {
return ParsedType::getFromOpaquePtr(Tok.getAnnotationValue());
@@ -531,9 +609,6 @@
}
};
- SourceLocation MatchRHSPunctuation(tok::TokenKind RHSTok,
- SourceLocation LHSLoc);
-
/// ExpectAndConsume - The parser expects that 'ExpectedTok' is next in the
/// input. If so, it is consumed and false is returned.
///
@@ -1220,10 +1295,8 @@
SourceLocation &RParenLoc);
ExprResult ParseCXXAmbiguousParenExpression(ParenParseOption &ExprType,
- ParsedType &CastTy,
- SourceLocation LParenLoc,
- SourceLocation &RParenLoc);
-
+ ParsedType &CastTy,
+ BalancedDelimiterTracker &Tracker);
ExprResult ParseCompoundLiteralExpression(ParsedType Ty,
SourceLocation LParenLoc,
SourceLocation RParenLoc);
@@ -1826,8 +1899,9 @@
bool CXX0XAttributesAllowed = true);
void ParseDirectDeclarator(Declarator &D);
void ParseParenDeclarator(Declarator &D);
- void ParseFunctionDeclarator(SourceLocation LParenLoc, Declarator &D,
+ void ParseFunctionDeclarator(Declarator &D,
ParsedAttributes &attrs,
+ BalancedDelimiterTracker &Tracker,
bool RequiresArg = false);
bool isFunctionDeclaratorIdentifierList();
void ParseFunctionDeclaratorIdentifierList(
@@ -1852,8 +1926,8 @@
std::vector<IdentifierInfo*>& Ident,
std::vector<SourceLocation>& NamespaceLoc,
unsigned int index, SourceLocation& InlineLoc,
- SourceLocation& LBrace, ParsedAttributes& attrs,
- SourceLocation& RBraceLoc);
+ ParsedAttributes& attrs,
+ BalancedDelimiterTracker &Tracker);
Decl *ParseLinkage(ParsingDeclSpec &DS, unsigned Context);
Decl *ParseUsingDirectiveOrDeclaration(unsigned Context,
const ParsedTemplateInfo &TemplateInfo,
diff --git a/lib/Parse/ParseDecl.cpp b/lib/Parse/ParseDecl.cpp
index 6de9e1b..228e53c 100644
--- a/lib/Parse/ParseDecl.cpp
+++ b/lib/Parse/ParseDecl.cpp
@@ -564,12 +564,11 @@
AvailabilityChange Changes[Unknown];
// Opening '('.
- SourceLocation LParenLoc;
- if (!Tok.is(tok::l_paren)) {
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.consumeOpen()) {
Diag(Tok, diag::err_expected_lparen);
return;
}
- LParenLoc = ConsumeParen();
// Parse the platform name,
if (Tok.isNot(tok::identifier)) {
@@ -667,12 +666,11 @@
} while (true);
// Closing ')'.
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
- if (RParenLoc.isInvalid())
+ if (T.consumeClose())
return;
if (endLoc)
- *endLoc = RParenLoc;
+ *endLoc = T.getCloseLocation();
// The 'unavailable' availability cannot be combined with any other
// availability changes. Make sure that hasn't happened.
@@ -694,7 +692,8 @@
}
// Record this attribute
- attrs.addNew(&Availability, SourceRange(AvailabilityLoc, RParenLoc),
+ attrs.addNew(&Availability,
+ SourceRange(AvailabilityLoc, T.getCloseLocation()),
0, SourceLocation(),
Platform, PlatformLoc,
Changes[Introduced],
@@ -840,8 +839,8 @@
SourceLocation *EndLoc) {
assert(Tok.is(tok::l_paren) && "Attribute arg list not starting with '('");
- SourceLocation LeftParenLoc = Tok.getLocation();
- ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
ExprVector ArgExprs(Actions);
bool ArgExprsOk = true;
@@ -851,7 +850,7 @@
ExprResult ArgExpr(ParseAssignmentExpression());
if (ArgExpr.isInvalid()) {
ArgExprsOk = false;
- MatchRHSPunctuation(tok::r_paren, LeftParenLoc);
+ T.consumeClose();
break;
} else {
ArgExprs.push_back(ArgExpr.release());
@@ -861,13 +860,12 @@
ConsumeToken(); // Eat the comma, move to the next argument
}
// Match the ')'.
- if (ArgExprsOk && Tok.is(tok::r_paren)) {
- if (EndLoc)
- *EndLoc = Tok.getLocation();
- ConsumeParen();
+ if (ArgExprsOk && !T.consumeClose()) {
Attrs.addNew(&AttrName, AttrNameLoc, 0, AttrNameLoc, 0, SourceLocation(),
ArgExprs.take(), ArgExprs.size());
}
+ if (EndLoc)
+ *EndLoc = T.getCloseLocation();
}
void Parser::DiagnoseProhibitedAttributes(ParsedAttributesWithRange &attrs) {
@@ -1241,7 +1239,9 @@
}
} else if (Tok.is(tok::l_paren)) {
// Parse C++ direct initializer: '(' expression-list ')'
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
ExprVector Exprs(Actions);
CommaLocsTy CommaLocs;
@@ -1259,7 +1259,7 @@
}
} else {
// Match the ')'.
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
assert(!Exprs.empty() && Exprs.size()-1 == CommaLocs.size() &&
"Unexpected number of commas!");
@@ -1269,9 +1269,9 @@
ExitScope();
}
- Actions.AddCXXDirectInitializerToDecl(ThisDecl, LParenLoc,
+ Actions.AddCXXDirectInitializerToDecl(ThisDecl, T.getOpenLocation(),
move_arg(Exprs),
- RParenLoc,
+ T.getCloseLocation(),
TypeContainsAuto);
}
} else if (getLang().CPlusPlus0x && Tok.is(tok::l_brace)) {
@@ -1532,24 +1532,24 @@
SourceLocation KWLoc = Tok.getLocation();
ConsumeToken();
- SourceLocation ParamLoc = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return;
- ExprResult ArgExpr = ParseAlignArgument(ParamLoc);
+ ExprResult ArgExpr = ParseAlignArgument(T.getOpenLocation());
if (ArgExpr.isInvalid()) {
SkipUntil(tok::r_paren);
return;
}
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, ParamLoc);
+ T.consumeClose();
if (endLoc)
- *endLoc = RParenLoc;
+ *endLoc = T.getCloseLocation();
ExprVector ArgExprs(Actions);
ArgExprs.push_back(ArgExpr.release());
Attrs.addNew(PP.getIdentifierInfo("aligned"), KWLoc, 0, KWLoc,
- 0, ParamLoc, ArgExprs.take(), 1, false, true);
+ 0, T.getOpenLocation(), ArgExprs.take(), 1, false, true);
}
/// ParseDeclarationSpecifiers
@@ -2626,7 +2626,9 @@
PrettyDeclStackTraceEntry CrashInfo(Actions, TagDecl, RecordLoc,
"parsing struct/union body");
- SourceLocation LBraceLoc = ConsumeBrace();
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ if (T.consumeOpen())
+ return;
ParseScope StructScope(this, Scope::ClassScope|Scope::DeclScope);
Actions.ActOnTagStartDefinition(getCurScope(), TagDecl);
@@ -2712,7 +2714,7 @@
}
}
- SourceLocation RBraceLoc = MatchRHSPunctuation(tok::r_brace, LBraceLoc);
+ T.consumeClose();
ParsedAttributes attrs(AttrFactory);
// If attributes exist after struct contents, parse them.
@@ -2720,10 +2722,11 @@
Actions.ActOnFields(getCurScope(),
RecordLoc, TagDecl, FieldDecls,
- LBraceLoc, RBraceLoc,
+ T.getOpenLocation(), T.getCloseLocation(),
attrs.getList());
StructScope.Exit();
- Actions.ActOnTagFinishDefinition(getCurScope(), TagDecl, RBraceLoc);
+ Actions.ActOnTagFinishDefinition(getCurScope(), TagDecl,
+ T.getCloseLocation());
}
/// ParseEnumSpecifier
@@ -2994,7 +2997,8 @@
ParseScope EnumScope(this, Scope::DeclScope);
Actions.ActOnTagStartDefinition(getCurScope(), EnumDecl);
- SourceLocation LBraceLoc = ConsumeBrace();
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ T.consumeOpen();
// C does not allow an empty enumerator-list, C++ does [dcl.enum].
if (Tok.is(tok::r_brace) && !getLang().CPlusPlus)
@@ -3051,18 +3055,20 @@
}
// Eat the }.
- SourceLocation RBraceLoc = MatchRHSPunctuation(tok::r_brace, LBraceLoc);
+ T.consumeClose();
// If attributes exist after the identifier list, parse them.
ParsedAttributes attrs(AttrFactory);
MaybeParseGNUAttributes(attrs);
- Actions.ActOnEnumBody(StartLoc, LBraceLoc, RBraceLoc, EnumDecl,
- EnumConstantDecls.data(), EnumConstantDecls.size(),
- getCurScope(), attrs.getList());
+ Actions.ActOnEnumBody(StartLoc, T.getOpenLocation(), T.getCloseLocation(),
+ EnumDecl, EnumConstantDecls.data(),
+ EnumConstantDecls.size(), getCurScope(),
+ attrs.getList());
EnumScope.Exit();
- Actions.ActOnTagFinishDefinition(getCurScope(), EnumDecl, RBraceLoc);
+ Actions.ActOnTagFinishDefinition(getCurScope(), EnumDecl,
+ T.getCloseLocation());
}
/// isTypeSpecifierQualifier - Return true if the current token could be the
@@ -3877,7 +3883,9 @@
break;
}
ParsedAttributes attrs(AttrFactory);
- ParseFunctionDeclarator(ConsumeParen(), D, attrs);
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+ ParseFunctionDeclarator(D, attrs, T);
} else if (Tok.is(tok::l_square)) {
ParseBracketDeclarator(D);
} else {
@@ -3900,7 +3908,9 @@
/// parameter-type-list[opt] ')'
///
void Parser::ParseParenDeclarator(Declarator &D) {
- SourceLocation StartLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
assert(!D.isPastIdentifier() && "Should be called before passing identifier");
// Eat any attributes before we look at whether this is a grouping or function
@@ -3963,9 +3973,10 @@
ParseDeclaratorInternal(D, &Parser::ParseDirectDeclarator);
// Match the ')'.
- SourceLocation EndLoc = MatchRHSPunctuation(tok::r_paren, StartLoc);
- D.AddTypeInfo(DeclaratorChunk::getParen(StartLoc, EndLoc),
- attrs, EndLoc);
+ T.consumeClose();
+ D.AddTypeInfo(DeclaratorChunk::getParen(T.getOpenLocation(),
+ T.getCloseLocation()),
+ attrs, T.getCloseLocation());
D.setGroupingParens(hadGroupingParens);
return;
@@ -3977,7 +3988,7 @@
// ParseFunctionDeclarator to handle of argument list.
D.SetIdentifier(0, Tok.getLocation());
- ParseFunctionDeclarator(StartLoc, D, attrs, RequiresArg);
+ ParseFunctionDeclarator(D, attrs, T, RequiresArg);
}
/// ParseFunctionDeclarator - We are after the identifier and have parsed the
@@ -3998,8 +4009,9 @@
/// dynamic-exception-specification
/// noexcept-specification
///
-void Parser::ParseFunctionDeclarator(SourceLocation LParenLoc, Declarator &D,
+void Parser::ParseFunctionDeclarator(Declarator &D,
ParsedAttributes &attrs,
+ BalancedDelimiterTracker &Tracker,
bool RequiresArg) {
// lparen is already consumed!
assert(D.isPastIdentifier() && "Should not call before identifier!");
@@ -4023,14 +4035,14 @@
ParsedType TrailingReturnType;
SourceLocation EndLoc;
-
if (isFunctionDeclaratorIdentifierList()) {
if (RequiresArg)
Diag(Tok, diag::err_argument_required_after_attribute);
ParseFunctionDeclaratorIdentifierList(D, ParamInfo);
- EndLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ Tracker.consumeClose();
+ EndLoc = Tracker.getCloseLocation();
} else {
// Enter function-declaration scope, limiting any declarators to the
// function prototype scope, including parameter declarators.
@@ -4045,7 +4057,8 @@
HasProto = ParamInfo.size() || getLang().CPlusPlus;
// If we have the closing ')', eat it.
- EndLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ Tracker.consumeClose();
+ EndLoc = Tracker.getCloseLocation();
if (getLang().CPlusPlus) {
MaybeParseCXX0XAttributes(attrs);
@@ -4101,7 +4114,8 @@
DynamicExceptions.size(),
NoexceptExpr.isUsable() ?
NoexceptExpr.get() : 0,
- LParenLoc, EndLoc, D,
+ Tracker.getOpenLocation(),
+ EndLoc, D,
TrailingReturnType),
attrs, EndLoc);
}
@@ -4235,7 +4249,7 @@
// Parse the declaration-specifiers.
// Just use the ParsingDeclaration "scope" of the declarator.
DeclSpec DS(AttrFactory);
-
+
// Skip any Microsoft attributes before a param.
if (getLang().MicrosoftExt && Tok.is(tok::l_square))
ParseMicrosoftAttributes(DS.getAttributes());
@@ -4369,20 +4383,22 @@
/// [C99] direct-declarator '[' type-qual-list 'static' assignment-expr ']'
/// [C99] direct-declarator '[' type-qual-list[opt] '*' ']'
void Parser::ParseBracketDeclarator(Declarator &D) {
- SourceLocation StartLoc = ConsumeBracket();
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
// C array syntax has many features, but by-far the most common is [] and [4].
// This code does a fast path to handle some of the most obvious cases.
if (Tok.getKind() == tok::r_square) {
- SourceLocation EndLoc = MatchRHSPunctuation(tok::r_square, StartLoc);
+ T.consumeClose();
ParsedAttributes attrs(AttrFactory);
MaybeParseCXX0XAttributes(attrs);
// Remember that we parsed the empty array type.
ExprResult NumElements;
D.AddTypeInfo(DeclaratorChunk::getArray(0, false, false, 0,
- StartLoc, EndLoc),
- attrs, EndLoc);
+ T.getOpenLocation(),
+ T.getCloseLocation()),
+ attrs, T.getCloseLocation());
return;
} else if (Tok.getKind() == tok::numeric_constant &&
GetLookAheadToken(1).is(tok::r_square)) {
@@ -4390,15 +4406,16 @@
ExprResult ExprRes(Actions.ActOnNumericConstant(Tok));
ConsumeToken();
- SourceLocation EndLoc = MatchRHSPunctuation(tok::r_square, StartLoc);
+ T.consumeClose();
ParsedAttributes attrs(AttrFactory);
MaybeParseCXX0XAttributes(attrs);
// Remember that we parsed a array type, and remember its features.
D.AddTypeInfo(DeclaratorChunk::getArray(0, false, 0,
ExprRes.release(),
- StartLoc, EndLoc),
- attrs, EndLoc);
+ T.getOpenLocation(),
+ T.getCloseLocation()),
+ attrs, T.getCloseLocation());
return;
}
@@ -4455,7 +4472,7 @@
return;
}
- SourceLocation EndLoc = MatchRHSPunctuation(tok::r_square, StartLoc);
+ T.consumeClose();
ParsedAttributes attrs(AttrFactory);
MaybeParseCXX0XAttributes(attrs);
@@ -4464,8 +4481,9 @@
D.AddTypeInfo(DeclaratorChunk::getArray(DS.getTypeQualifiers(),
StaticLoc.isValid(), isStar,
NumElements.release(),
- StartLoc, EndLoc),
- attrs, EndLoc);
+ T.getOpenLocation(),
+ T.getCloseLocation()),
+ attrs, T.getCloseLocation());
}
/// [GNU] typeof-specifier:
@@ -4530,10 +4548,8 @@
assert(Tok.is(tok::kw__Atomic) && "Not an atomic specifier");
SourceLocation StartLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
-
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen_after,
- "_Atomic")) {
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen_after, "_Atomic")) {
SkipUntil(tok::r_paren);
return;
}
@@ -4545,17 +4561,13 @@
}
// Match the ')'
- SourceLocation RParenLoc;
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
- if (RParenLoc.isInvalid())
+ if (T.getCloseLocation().isInvalid())
return;
- DS.setTypeofParensRange(SourceRange(LParenLoc, RParenLoc));
- DS.SetRangeEnd(RParenLoc);
+ DS.setTypeofParensRange(T.getRange());
+ DS.SetRangeEnd(T.getCloseLocation());
const char *PrevSpec = 0;
unsigned DiagID;
diff --git a/lib/Parse/ParseDeclCXX.cpp b/lib/Parse/ParseDeclCXX.cpp
index 45e6251..51cdf6b 100644
--- a/lib/Parse/ParseDeclCXX.cpp
+++ b/lib/Parse/ParseDeclCXX.cpp
@@ -95,7 +95,8 @@
}
- if (Tok.isNot(tok::l_brace)) {
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ if (T.consumeOpen()) {
if (!ExtraIdent.empty()) {
Diag(ExtraNamespaceLoc[0], diag::err_nested_namespaces_with_double_colon)
<< SourceRange(ExtraNamespaceLoc.front(), ExtraIdentLoc.back());
@@ -105,8 +106,6 @@
return 0;
}
- SourceLocation LBrace = ConsumeBrace();
-
if (getCurScope()->isClassScope() || getCurScope()->isTemplateParamScope() ||
getCurScope()->isInObjcMethodScope() || getCurScope()->getBlockParent() ||
getCurScope()->getFnParent()) {
@@ -114,7 +113,7 @@
Diag(ExtraNamespaceLoc[0], diag::err_nested_namespaces_with_double_colon)
<< SourceRange(ExtraNamespaceLoc.front(), ExtraIdentLoc.back());
}
- Diag(LBrace, diag::err_namespace_nonnamespace_scope);
+ Diag(T.getOpenLocation(), diag::err_namespace_nonnamespace_scope);
SkipUntil(tok::r_brace, false);
return 0;
}
@@ -157,23 +156,23 @@
Decl *NamespcDecl =
Actions.ActOnStartNamespaceDef(getCurScope(), InlineLoc, NamespaceLoc,
- IdentLoc, Ident, LBrace, attrs.getList());
+ IdentLoc, Ident, T.getOpenLocation(),
+ attrs.getList());
PrettyDeclStackTraceEntry CrashInfo(Actions, NamespcDecl, NamespaceLoc,
"parsing namespace");
- SourceLocation RBraceLoc;
// Parse the contents of the namespace. This includes parsing recovery on
// any improperly nested namespaces.
ParseInnerNamespace(ExtraIdentLoc, ExtraIdent, ExtraNamespaceLoc, 0,
- InlineLoc, LBrace, attrs, RBraceLoc);
+ InlineLoc, attrs, T);
// Leave the namespace scope.
NamespaceScope.Exit();
- Actions.ActOnFinishNamespaceDef(NamespcDecl, RBraceLoc);
+ DeclEnd = T.getCloseLocation();
+ Actions.ActOnFinishNamespaceDef(NamespcDecl, DeclEnd);
- DeclEnd = RBraceLoc;
return NamespcDecl;
}
@@ -182,9 +181,8 @@
std::vector<IdentifierInfo*>& Ident,
std::vector<SourceLocation>& NamespaceLoc,
unsigned int index, SourceLocation& InlineLoc,
- SourceLocation& LBrace,
ParsedAttributes& attrs,
- SourceLocation& RBraceLoc) {
+ BalancedDelimiterTracker &Tracker) {
if (index == Ident.size()) {
while (Tok.isNot(tok::r_brace) && Tok.isNot(tok::eof)) {
ParsedAttributesWithRange attrs(AttrFactory);
@@ -192,7 +190,10 @@
MaybeParseMicrosoftAttributes(attrs);
ParseExternalDeclaration(attrs);
}
- RBraceLoc = MatchRHSPunctuation(tok::r_brace, LBrace);
+
+ // The caller is what called check -- we are simply calling
+ // the close for it.
+ Tracker.consumeClose();
return;
}
@@ -202,14 +203,15 @@
Decl *NamespcDecl =
Actions.ActOnStartNamespaceDef(getCurScope(), SourceLocation(),
NamespaceLoc[index], IdentLoc[index],
- Ident[index], LBrace, attrs.getList());
+ Ident[index], Tracker.getOpenLocation(),
+ attrs.getList());
ParseInnerNamespace(IdentLoc, Ident, NamespaceLoc, ++index, InlineLoc,
- LBrace, attrs, RBraceLoc);
+ attrs, Tracker);
NamespaceScope.Exit();
- Actions.ActOnFinishNamespaceDef(NamespcDecl, RBraceLoc);
+ Actions.ActOnFinishNamespaceDef(NamespcDecl, Tracker.getCloseLocation());
}
/// ParseNamespaceAlias - Parse the part after the '=' in a namespace
@@ -298,7 +300,8 @@
ProhibitAttributes(attrs);
- SourceLocation LBrace = ConsumeBrace();
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ T.consumeOpen();
while (Tok.isNot(tok::r_brace) && Tok.isNot(tok::eof)) {
ParsedAttributesWithRange attrs(AttrFactory);
MaybeParseCXX0XAttributes(attrs);
@@ -306,9 +309,9 @@
ParseExternalDeclaration(attrs);
}
- SourceLocation RBrace = MatchRHSPunctuation(tok::r_brace, LBrace);
+ T.consumeClose();
return Actions.ActOnFinishLinkageSpecification(getCurScope(), LinkageSpec,
- RBrace);
+ T.getCloseLocation());
}
/// ParseUsingDirectiveOrDeclaration - Parse C++ using using-declaration or
@@ -585,13 +588,12 @@
SourceLocation StaticAssertLoc = ConsumeToken();
- if (Tok.isNot(tok::l_paren)) {
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.consumeOpen()) {
Diag(Tok, diag::err_expected_lparen);
return 0;
}
- SourceLocation LParenLoc = ConsumeParen();
-
ExprResult AssertExpr(ParseConstantExpression());
if (AssertExpr.isInvalid()) {
SkipUntil(tok::semi);
@@ -611,7 +613,7 @@
if (AssertMessage.isInvalid())
return 0;
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
DeclEnd = Tok.getLocation();
ExpectAndConsumeSemi(diag::err_expected_semi_after_static_assert);
@@ -619,7 +621,7 @@
return Actions.ActOnStaticAssertDeclaration(StaticAssertLoc,
AssertExpr.take(),
AssertMessage.take(),
- RParenLoc);
+ T.getCloseLocation());
}
/// ParseDecltypeSpecifier - Parse a C++0x decltype specifier.
@@ -630,11 +632,9 @@
assert(Tok.is(tok::kw_decltype) && "Not a decltype specifier");
SourceLocation StartLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
-
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen_after,
- "decltype")) {
- SkipUntil(tok::r_paren);
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen_after,
+ "decltype", tok::r_paren)) {
return;
}
@@ -651,13 +651,8 @@
}
// Match the ')'
- SourceLocation RParenLoc;
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
-
- if (RParenLoc.isInvalid())
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return;
const char *PrevSpec = 0;
@@ -673,11 +668,9 @@
"Not an underlying type specifier");
SourceLocation StartLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
-
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen_after,
- "__underlying_type")) {
- SkipUntil(tok::r_paren);
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen_after,
+ "__underlying_type", tok::r_paren)) {
return;
}
@@ -688,13 +681,8 @@
}
// Match the ')'
- SourceLocation RParenLoc;
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
-
- if (RParenLoc.isInvalid())
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return;
const char *PrevSpec = 0;
@@ -2106,12 +2094,12 @@
}
assert(Tok.is(tok::l_brace));
-
- SourceLocation LBraceLoc = ConsumeBrace();
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ T.consumeOpen();
if (TagDecl)
Actions.ActOnStartCXXMemberDeclarations(getCurScope(), TagDecl, FinalLoc,
- LBraceLoc);
+ T.getOpenLocation());
// C++ 11p3: Members of a class defined with the keyword class are private
// by default. Members of a class defined with the keywords struct or union
@@ -2122,7 +2110,6 @@
else
CurAS = AS_public;
- SourceLocation RBraceLoc;
if (TagDecl) {
// While we still have something to read, read the member-declarations.
while (Tok.isNot(tok::r_brace) && Tok.isNot(tok::eof)) {
@@ -2163,7 +2150,7 @@
ParseCXXClassMemberDeclaration(CurAS);
}
- RBraceLoc = MatchRHSPunctuation(tok::r_brace, LBraceLoc);
+ T.consumeClose();
} else {
SkipUntil(tok::r_brace, false, false);
}
@@ -2174,7 +2161,8 @@
if (TagDecl)
Actions.ActOnFinishCXXMemberSpecification(getCurScope(), RecordLoc, TagDecl,
- LBraceLoc, RBraceLoc,
+ T.getOpenLocation(),
+ T.getCloseLocation(),
attrs.getList());
// C++0x [class.mem]p2: Within the class member-specification, the class is
@@ -2198,7 +2186,8 @@
}
if (TagDecl)
- Actions.ActOnTagFinishDefinition(getCurScope(), TagDecl, RBraceLoc);
+ Actions.ActOnTagFinishDefinition(getCurScope(), TagDecl,
+ T.getCloseLocation());
// Leave the class scope.
ParsingDef.Pop();
@@ -2323,7 +2312,8 @@
TemplateTypeTy, IdLoc, InitList.take(),
EllipsisLoc);
} else if(Tok.is(tok::l_paren)) {
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
// Parse the optional expression-list.
ExprVector ArgExprs(Actions);
@@ -2333,7 +2323,7 @@
return true;
}
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
SourceLocation EllipsisLoc;
if (Tok.is(tok::ellipsis))
@@ -2341,8 +2331,8 @@
return Actions.ActOnMemInitializer(ConstructorDecl, getCurScope(), SS, II,
TemplateTypeTy, IdLoc,
- LParenLoc, ArgExprs.take(),
- ArgExprs.size(), RParenLoc,
+ T.getOpenLocation(), ArgExprs.take(),
+ ArgExprs.size(), T.getCloseLocation(),
EllipsisLoc);
}
@@ -2388,7 +2378,8 @@
SourceLocation KeywordLoc = ConsumeToken();
if (Tok.is(tok::l_paren)) {
// There is an argument.
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
NoexceptType = EST_ComputedNoexcept;
NoexceptExpr = ParseConstantExpression();
// The argument must be contextually convertible to bool. We use
@@ -2396,8 +2387,8 @@
if (!NoexceptExpr.isInvalid())
NoexceptExpr = Actions.ActOnBooleanCondition(getCurScope(), KeywordLoc,
NoexceptExpr.get());
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
- NoexceptRange = SourceRange(KeywordLoc, RParenLoc);
+ T.consumeClose();
+ NoexceptRange = SourceRange(KeywordLoc, T.getCloseLocation());
} else {
// There is no argument.
NoexceptType = EST_BasicNoexcept;
@@ -2440,13 +2431,12 @@
assert(Tok.is(tok::kw_throw) && "expected throw");
SpecificationRange.setBegin(ConsumeToken());
-
- if (!Tok.is(tok::l_paren)) {
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.consumeOpen()) {
Diag(Tok, diag::err_expected_lparen_after) << "throw";
SpecificationRange.setEnd(SpecificationRange.getBegin());
return EST_DynamicNone;
}
- SourceLocation LParenLoc = ConsumeParen();
// Parse throw(...), a Microsoft extension that means "this function
// can throw anything".
@@ -2454,8 +2444,8 @@
SourceLocation EllipsisLoc = ConsumeToken();
if (!getLang().MicrosoftExt)
Diag(EllipsisLoc, diag::ext_ellipsis_exception_spec);
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
- SpecificationRange.setEnd(RParenLoc);
+ T.consumeClose();
+ SpecificationRange.setEnd(T.getCloseLocation());
return EST_MSAny;
}
@@ -2485,7 +2475,8 @@
break;
}
- SpecificationRange.setEnd(MatchRHSPunctuation(tok::r_paren, LParenLoc));
+ T.consumeClose();
+ SpecificationRange.setEnd(T.getCloseLocation());
return Exceptions.empty() ? EST_DynamicNone : EST_Dynamic;
}
diff --git a/lib/Parse/ParseExpr.cpp b/lib/Parse/ParseExpr.cpp
index 7380401..548a599 100644
--- a/lib/Parse/ParseExpr.cpp
+++ b/lib/Parse/ParseExpr.cpp
@@ -1028,18 +1028,21 @@
case tok::kw_noexcept: { // [C++0x] 'noexcept' '(' expression ')'
SourceLocation KeyLoc = ConsumeToken();
- SourceLocation LParen = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren,
- diag::err_expected_lparen_after, "noexcept"))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+
+ if (T.expectAndConsume(diag::err_expected_lparen_after, "noexcept"))
return ExprError();
// C++ [expr.unary.noexcept]p1:
// The noexcept operator determines whether the evaluation of its operand,
// which is an unevaluated operand, can throw an exception.
EnterExpressionEvaluationContext Unevaluated(Actions, Sema::Unevaluated);
ExprResult Result = ParseExpression();
- SourceLocation RParen = MatchRHSPunctuation(tok::r_paren, LParen);
+
+ T.consumeClose();
+
if (!Result.isInvalid())
- Result = Actions.ActOnNoexceptExpr(KeyLoc, LParen, Result.take(), RParen);
+ Result = Actions.ActOnNoexceptExpr(KeyLoc, T.getOpenLocation(),
+ Result.take(), T.getCloseLocation());
return move(Result);
}
@@ -1198,8 +1201,10 @@
if (getLang().ObjC1 && Tok.isAtStartOfLine() &&
isSimpleObjCMessageExpression())
return move(LHS);
-
- Loc = ConsumeBracket();
+
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
+ Loc = T.getOpenLocation();
ExprResult Idx;
if (getLang().CPlusPlus0x && Tok.is(tok::l_brace))
Idx = ParseBraceInitializer();
@@ -1215,7 +1220,7 @@
LHS = ExprError();
// Match the ']'.
- MatchRHSPunctuation(tok::r_square, Loc);
+ T.consumeClose();
break;
}
@@ -1227,12 +1232,13 @@
Expr *ExecConfig = 0;
+ BalancedDelimiterTracker LLLT(*this, tok::lesslessless);
+ BalancedDelimiterTracker PT(*this, tok::l_paren);
+
if (OpKind == tok::lesslessless) {
ExprVector ExecConfigExprs(Actions);
CommaLocsTy ExecConfigCommaLocs;
- SourceLocation LLLLoc, GGGLoc;
-
- LLLLoc = ConsumeToken();
+ LLLT.consumeOpen();
if (ParseExpressionList(ExecConfigExprs, ExecConfigCommaLocs)) {
LHS = ExprError();
@@ -1240,11 +1246,9 @@
if (LHS.isInvalid()) {
SkipUntil(tok::greatergreatergreater);
- } else if (Tok.isNot(tok::greatergreatergreater)) {
- MatchRHSPunctuation(tok::greatergreatergreater, LLLLoc);
+ } else if (LLLT.consumeClose()) {
+ // There was an error closing the brackets
LHS = ExprError();
- } else {
- GGGLoc = ConsumeToken();
}
if (!LHS.isInvalid()) {
@@ -1256,14 +1260,17 @@
if (!LHS.isInvalid()) {
ExprResult ECResult = Actions.ActOnCUDAExecConfigExpr(getCurScope(),
- LLLLoc, move_arg(ExecConfigExprs), GGGLoc);
+ LLLT.getOpenLocation(),
+ move_arg(ExecConfigExprs),
+ LLLT.getCloseLocation());
if (ECResult.isInvalid())
LHS = ExprError();
else
ExecConfig = ECResult.get();
}
} else {
- Loc = ConsumeParen();
+ PT.consumeOpen();
+ Loc = PT.getOpenLocation();
}
ExprVector ArgExprs(Actions);
@@ -1288,7 +1295,7 @@
if (LHS.isInvalid()) {
SkipUntil(tok::r_paren);
} else if (Tok.isNot(tok::r_paren)) {
- MatchRHSPunctuation(tok::r_paren, Loc);
+ PT.consumeClose();
LHS = ExprError();
} else {
assert((ArgExprs.size() == 0 ||
@@ -1297,7 +1304,7 @@
LHS = Actions.ActOnCallExpr(getCurScope(), LHS.take(), Loc,
move_arg(ArgExprs), Tok.getLocation(),
ExecConfig);
- ConsumeParen();
+ PT.consumeClose();
}
break;
@@ -1490,11 +1497,14 @@
IdentifierInfo *Name = 0;
SourceLocation NameLoc;
if (Tok.is(tok::l_paren)) {
- LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+ LParenLoc = T.getOpenLocation();
if (Tok.is(tok::identifier)) {
Name = Tok.getIdentifierInfo();
NameLoc = ConsumeToken();
- RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
+ RParenLoc = T.getCloseLocation();
if (RParenLoc.isInvalid())
RParenLoc = PP.getLocForEndOfToken(NameLoc);
} else {
@@ -1581,7 +1591,9 @@
return ExprError(Diag(Tok, diag::err_expected_lparen_after_id)
<< BuiltinII);
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker PT(*this, tok::l_paren);
+ PT.consumeOpen();
+
// TODO: Build AST.
switch (T) {
@@ -1651,7 +1663,9 @@
// offsetof-member-designator: offsetof-member-design '[' expression ']'
Comps.push_back(Sema::OffsetOfComponent());
Comps.back().isBrackets = true;
- Comps.back().LocStart = ConsumeBracket();
+ BalancedDelimiterTracker ST(*this, tok::l_square);
+ ST.consumeOpen();
+ Comps.back().LocStart = ST.getOpenLocation();
Res = ParseExpression();
if (Res.isInvalid()) {
SkipUntil(tok::r_paren);
@@ -1659,18 +1673,19 @@
}
Comps.back().U.E = Res.release();
- Comps.back().LocEnd =
- MatchRHSPunctuation(tok::r_square, Comps.back().LocStart);
+ ST.consumeClose();
+ Comps.back().LocEnd = ST.getCloseLocation();
} else {
if (Tok.isNot(tok::r_paren)) {
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ PT.consumeClose();
Res = ExprError();
} else if (Ty.isInvalid()) {
Res = ExprError();
} else {
+ PT.consumeClose();
Res = Actions.ActOnBuiltinOffsetOf(getCurScope(), StartLoc, TypeLoc,
- Ty.get(), &Comps[0],
- Comps.size(), ConsumeParen());
+ Ty.get(), &Comps[0], Comps.size(),
+ PT.getCloseLocation());
}
break;
}
@@ -1770,7 +1785,11 @@
SourceLocation &RParenLoc) {
assert(Tok.is(tok::l_paren) && "Not a paren expr!");
GreaterThanIsOperatorScope G(GreaterThanIsOperator, true);
- SourceLocation OpenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.consumeOpen())
+ return ExprError();
+ SourceLocation OpenLoc = T.getOpenLocation();
+
ExprResult Result(true);
bool isAmbiguousTypeId;
CastTy = ParsedType();
@@ -1823,7 +1842,8 @@
}
TypeResult Ty = ParseTypeName();
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, OpenLoc);
+ T.consumeClose();
+ RParenLoc = T.getCloseLocation();
ExprResult SubExpr = ParseCastExpression(/*isUnaryExpression=*/false);
if (Ty.isInvalid() || SubExpr.isInvalid())
@@ -1842,9 +1862,11 @@
// in which case we should treat it as type-id.
// if stopIfCastExpr is false, we need to determine the context past the
// parens, so we defer to ParseCXXAmbiguousParenExpression for that.
- if (isAmbiguousTypeId && !stopIfCastExpr)
- return ParseCXXAmbiguousParenExpression(ExprType, CastTy,
- OpenLoc, RParenLoc);
+ if (isAmbiguousTypeId && !stopIfCastExpr) {
+ ExprResult res = ParseCXXAmbiguousParenExpression(ExprType, CastTy, T);
+ RParenLoc = T.getCloseLocation();
+ return res;
+ }
// Parse the type declarator.
DeclSpec DS(AttrFactory);
@@ -1868,11 +1890,8 @@
Ty.get(), 0);
} else {
// Match the ')'.
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, OpenLoc);
-
+ T.consumeClose();
+ RParenLoc = T.getCloseLocation();
if (Tok.is(tok::l_brace)) {
ExprType = CompoundLiteral;
TypeResult Ty;
@@ -1956,11 +1975,8 @@
return ExprError();
}
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, OpenLoc);
-
+ T.consumeClose();
+ RParenLoc = T.getCloseLocation();
return move(Result);
}
@@ -2024,8 +2040,8 @@
if (!getLang().C1X)
Diag(KeyLoc, diag::ext_c1x_generic_selection);
- SourceLocation LParenLoc = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen, ""))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return ExprError();
ExprResult ControllingExpr;
@@ -2091,11 +2107,12 @@
ConsumeToken();
}
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
- if (RParenLoc.isInvalid())
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return ExprError();
- return Actions.ActOnGenericSelectionExpr(KeyLoc, DefaultLoc, RParenLoc,
+ return Actions.ActOnGenericSelectionExpr(KeyLoc, DefaultLoc,
+ T.getCloseLocation(),
ControllingExpr.release(),
move_arg(Types), move_arg(Exprs));
}
diff --git a/lib/Parse/ParseExprCXX.cpp b/lib/Parse/ParseExprCXX.cpp
index fef52a5..6e36c91 100644
--- a/lib/Parse/ParseExprCXX.cpp
+++ b/lib/Parse/ParseExprCXX.cpp
@@ -594,7 +594,10 @@
typedef llvm::Optional<unsigned> DiagResult;
assert(Tok.is(tok::l_square) && "Lambda expressions begin with '['.");
- Intro.Range.setBegin(ConsumeBracket());
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
+
+ Intro.Range.setBegin(T.getOpenLocation());
bool first = true;
@@ -649,8 +652,8 @@
Intro.addCapture(Kind, Loc, Id);
}
- Intro.Range.setEnd(MatchRHSPunctuation(tok::r_square,
- Intro.Range.getBegin()));
+ T.consumeClose();
+ Intro.Range.setEnd(T.getCloseLocation());
return DiagResult();
}
@@ -685,7 +688,10 @@
Scope::FunctionPrototypeScope |
Scope::DeclScope);
- SourceLocation DeclLoc = ConsumeParen(), DeclEndLoc;
+ SourceLocation DeclLoc, DeclEndLoc;
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+ DeclLoc = T.getOpenLocation();
// Parse parameter-declaration-clause.
ParsedAttributes Attr(AttrFactory);
@@ -695,7 +701,8 @@
if (Tok.isNot(tok::r_paren))
ParseParameterDeclarationClause(D, Attr, ParamInfo, EllipsisLoc);
- DeclEndLoc = MatchRHSPunctuation(tok::r_paren, DeclLoc);
+ T.consumeClose();
+ DeclEndLoc = T.getCloseLocation();
// Parse 'mutable'[opt].
SourceLocation MutableLoc;
@@ -816,21 +823,23 @@
if (ExpectAndConsume(tok::greater, diag::err_expected_greater))
return ExprError(Diag(LAngleBracketLoc, diag::note_matching) << "<");
- SourceLocation LParenLoc = Tok.getLocation(), RParenLoc;
+ SourceLocation LParenLoc, RParenLoc;
+ BalancedDelimiterTracker T(*this, tok::l_paren);
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen_after, CastName))
+ if (T.expectAndConsume(diag::err_expected_lparen_after, CastName))
return ExprError();
ExprResult Result = ParseExpression();
// Match the ')'.
- RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
if (!Result.isInvalid() && !DeclaratorInfo.isInvalidType())
Result = Actions.ActOnCXXNamedCast(OpLoc, Kind,
LAngleBracketLoc, DeclaratorInfo,
RAngleBracketLoc,
- LParenLoc, Result.take(), RParenLoc);
+ T.getOpenLocation(), Result.take(),
+ T.getCloseLocation());
return move(Result);
}
@@ -845,13 +854,13 @@
assert(Tok.is(tok::kw_typeid) && "Not 'typeid'!");
SourceLocation OpLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
- SourceLocation RParenLoc;
+ SourceLocation LParenLoc, RParenLoc;
+ BalancedDelimiterTracker T(*this, tok::l_paren);
// typeid expressions are always parenthesized.
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen_after,
- "typeid"))
+ if (T.expectAndConsume(diag::err_expected_lparen_after, "typeid"))
return ExprError();
+ LParenLoc = T.getOpenLocation();
ExprResult Result;
@@ -859,8 +868,8 @@
TypeResult Ty = ParseTypeName();
// Match the ')'.
- RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
-
+ T.consumeClose();
+ RParenLoc = T.getCloseLocation();
if (Ty.isInvalid() || RParenLoc.isInvalid())
return ExprError();
@@ -883,7 +892,8 @@
if (Result.isInvalid())
SkipUntil(tok::r_paren);
else {
- RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
+ RParenLoc = T.getCloseLocation();
if (RParenLoc.isInvalid())
return ExprError();
@@ -904,12 +914,10 @@
assert(Tok.is(tok::kw___uuidof) && "Not '__uuidof'!");
SourceLocation OpLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
- SourceLocation RParenLoc;
+ BalancedDelimiterTracker T(*this, tok::l_paren);
// __uuidof expressions are always parenthesized.
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen_after,
- "__uuidof"))
+ if (T.expectAndConsume(diag::err_expected_lparen_after, "__uuidof"))
return ExprError();
ExprResult Result;
@@ -918,13 +926,14 @@
TypeResult Ty = ParseTypeName();
// Match the ')'.
- RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
if (Ty.isInvalid())
return ExprError();
- Result = Actions.ActOnCXXUuidof(OpLoc, LParenLoc, /*isType=*/true,
- Ty.get().getAsOpaquePtr(), RParenLoc);
+ Result = Actions.ActOnCXXUuidof(OpLoc, T.getOpenLocation(), /*isType=*/true,
+ Ty.get().getAsOpaquePtr(),
+ T.getCloseLocation());
} else {
EnterExpressionEvaluationContext Unevaluated(Actions, Sema::Unevaluated);
Result = ParseExpression();
@@ -933,10 +942,11 @@
if (Result.isInvalid())
SkipUntil(tok::r_paren);
else {
- RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
- Result = Actions.ActOnCXXUuidof(OpLoc, LParenLoc, /*isType=*/false,
- Result.release(), RParenLoc);
+ Result = Actions.ActOnCXXUuidof(OpLoc, T.getOpenLocation(),
+ /*isType=*/false,
+ Result.release(), T.getCloseLocation());
}
}
@@ -1093,7 +1103,8 @@
} else {
GreaterThanIsOperatorScope G(GreaterThanIsOperator, true);
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
ExprVector Exprs(Actions);
CommaLocsTy CommaLocs;
@@ -1106,7 +1117,7 @@
}
// Match the ')'.
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
// TypeRep could be null, if it references an invalid typedef.
if (!TypeRep)
@@ -1114,8 +1125,9 @@
assert((Exprs.size() == 0 || Exprs.size()-1 == CommaLocs.size())&&
"Unexpected number of commas!");
- return Actions.ActOnCXXTypeConstructExpr(TypeRep, LParenLoc, move_arg(Exprs),
- RParenLoc);
+ return Actions.ActOnCXXTypeConstructExpr(TypeRep, T.getOpenLocation(),
+ move_arg(Exprs),
+ T.getCloseLocation());
}
}
@@ -1651,16 +1663,15 @@
// Consume the 'new' or 'delete'.
SymbolLocations[SymbolIdx++] = ConsumeToken();
if (Tok.is(tok::l_square)) {
- // Consume the '['.
- SourceLocation LBracketLoc = ConsumeBracket();
- // Consume the ']'.
- SourceLocation RBracketLoc = MatchRHSPunctuation(tok::r_square,
- LBracketLoc);
- if (RBracketLoc.isInvalid())
+ // Consume the '[' and ']'.
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return true;
- SymbolLocations[SymbolIdx++] = LBracketLoc;
- SymbolLocations[SymbolIdx++] = RBracketLoc;
+ SymbolLocations[SymbolIdx++] = T.getOpenLocation();
+ SymbolLocations[SymbolIdx++] = T.getCloseLocation();
Op = isNew? OO_Array_New : OO_Array_Delete;
} else {
Op = isNew? OO_New : OO_Delete;
@@ -1677,31 +1688,29 @@
#include "clang/Basic/OperatorKinds.def"
case tok::l_paren: {
- // Consume the '('.
- SourceLocation LParenLoc = ConsumeParen();
- // Consume the ')'.
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren,
- LParenLoc);
- if (RParenLoc.isInvalid())
+ // Consume the '(' and ')'.
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return true;
- SymbolLocations[SymbolIdx++] = LParenLoc;
- SymbolLocations[SymbolIdx++] = RParenLoc;
+ SymbolLocations[SymbolIdx++] = T.getOpenLocation();
+ SymbolLocations[SymbolIdx++] = T.getCloseLocation();
Op = OO_Call;
break;
}
case tok::l_square: {
- // Consume the '['.
- SourceLocation LBracketLoc = ConsumeBracket();
- // Consume the ']'.
- SourceLocation RBracketLoc = MatchRHSPunctuation(tok::r_square,
- LBracketLoc);
- if (RBracketLoc.isInvalid())
+ // Consume the '[' and ']'.
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return true;
- SymbolLocations[SymbolIdx++] = LBracketLoc;
- SymbolLocations[SymbolIdx++] = RBracketLoc;
+ SymbolLocations[SymbolIdx++] = T.getOpenLocation();
+ SymbolLocations[SymbolIdx++] = T.getCloseLocation();
Op = OO_Subscript;
break;
}
@@ -2012,13 +2021,16 @@
Declarator DeclaratorInfo(DS, Declarator::CXXNewContext);
if (Tok.is(tok::l_paren)) {
// If it turns out to be a placement, we change the type location.
- PlacementLParen = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+ PlacementLParen = T.getOpenLocation();
if (ParseExpressionListOrTypeId(PlacementArgs, DeclaratorInfo)) {
SkipUntil(tok::semi, /*StopAtSemi=*/true, /*DontConsume=*/true);
return ExprError();
}
- PlacementRParen = MatchRHSPunctuation(tok::r_paren, PlacementLParen);
+ T.consumeClose();
+ PlacementRParen = T.getCloseLocation();
if (PlacementRParen.isInvalid()) {
SkipUntil(tok::semi, /*StopAtSemi=*/true, /*DontConsume=*/true);
return ExprError();
@@ -2026,18 +2038,19 @@
if (PlacementArgs.empty()) {
// Reset the placement locations. There was no placement.
- TypeIdParens = SourceRange(PlacementLParen, PlacementRParen);
+ TypeIdParens = T.getRange();
PlacementLParen = PlacementRParen = SourceLocation();
} else {
// We still need the type.
if (Tok.is(tok::l_paren)) {
- TypeIdParens.setBegin(ConsumeParen());
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
MaybeParseGNUAttributes(DeclaratorInfo);
ParseSpecifierQualifierList(DS);
DeclaratorInfo.SetSourceRange(DS.getSourceRange());
ParseDeclarator(DeclaratorInfo);
- TypeIdParens.setEnd(MatchRHSPunctuation(tok::r_paren,
- TypeIdParens.getBegin()));
+ T.consumeClose();
+ TypeIdParens = T.getRange();
} else {
MaybeParseGNUAttributes(DeclaratorInfo);
if (ParseCXXTypeSpecifierSeq(DS))
@@ -2070,7 +2083,9 @@
SourceLocation ConstructorLParen, ConstructorRParen;
if (Tok.is(tok::l_paren)) {
- ConstructorLParen = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+ ConstructorLParen = T.getOpenLocation();
if (Tok.isNot(tok::r_paren)) {
CommaLocsTy CommaLocs;
if (ParseExpressionList(ConstructorArgs, CommaLocs)) {
@@ -2078,7 +2093,8 @@
return ExprError();
}
}
- ConstructorRParen = MatchRHSPunctuation(tok::r_paren, ConstructorLParen);
+ T.consumeClose();
+ ConstructorRParen = T.getCloseLocation();
if (ConstructorRParen.isInvalid()) {
SkipUntil(tok::semi, /*StopAtSemi=*/true, /*DontConsume=*/true);
return ExprError();
@@ -2105,7 +2121,9 @@
// Parse the array dimensions.
bool first = true;
while (Tok.is(tok::l_square)) {
- SourceLocation LLoc = ConsumeBracket();
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
+
ExprResult Size(first ? ParseExpression()
: ParseConstantExpression());
if (Size.isInvalid()) {
@@ -2115,15 +2133,17 @@
}
first = false;
- SourceLocation RLoc = MatchRHSPunctuation(tok::r_square, LLoc);
+ T.consumeClose();
ParsedAttributes attrs(AttrFactory);
D.AddTypeInfo(DeclaratorChunk::getArray(0,
/*static=*/false, /*star=*/false,
- Size.release(), LLoc, RLoc),
- attrs, RLoc);
+ Size.release(),
+ T.getOpenLocation(),
+ T.getCloseLocation()),
+ attrs, T.getCloseLocation());
- if (RLoc.isInvalid())
+ if (T.getCloseLocation().isInvalid())
return;
}
}
@@ -2175,9 +2195,11 @@
bool ArrayDelete = false;
if (Tok.is(tok::l_square)) {
ArrayDelete = true;
- SourceLocation LHS = ConsumeBracket();
- SourceLocation RHS = MatchRHSPunctuation(tok::r_square, LHS);
- if (RHS.isInvalid())
+ BalancedDelimiterTracker T(*this, tok::l_square);
+
+ T.consumeOpen();
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return ExprError();
}
@@ -2275,8 +2297,8 @@
UnaryTypeTrait UTT = UnaryTypeTraitFromTokKind(Tok.getKind());
SourceLocation Loc = ConsumeToken();
- SourceLocation LParen = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return ExprError();
// FIXME: Error reporting absolutely sucks! If the this fails to parse a type
@@ -2284,12 +2306,12 @@
// specifiers.
TypeResult Ty = ParseTypeName();
- SourceLocation RParen = MatchRHSPunctuation(tok::r_paren, LParen);
+ T.consumeClose();
if (Ty.isInvalid())
return ExprError();
- return Actions.ActOnUnaryTypeTrait(UTT, Loc, Ty.get(), RParen);
+ return Actions.ActOnUnaryTypeTrait(UTT, Loc, Ty.get(), T.getCloseLocation());
}
/// ParseBinaryTypeTrait - Parse the built-in binary type-trait
@@ -2303,8 +2325,8 @@
BinaryTypeTrait BTT = BinaryTypeTraitFromTokKind(Tok.getKind());
SourceLocation Loc = ConsumeToken();
- SourceLocation LParen = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return ExprError();
TypeResult LhsTy = ParseTypeName();
@@ -2324,9 +2346,10 @@
return ExprError();
}
- SourceLocation RParen = MatchRHSPunctuation(tok::r_paren, LParen);
+ T.consumeClose();
- return Actions.ActOnBinaryTypeTrait(BTT, Loc, LhsTy.get(), RhsTy.get(), RParen);
+ return Actions.ActOnBinaryTypeTrait(BTT, Loc, LhsTy.get(), RhsTy.get(),
+ T.getCloseLocation());
}
/// ParseArrayTypeTrait - Parse the built-in array type-trait
@@ -2340,8 +2363,8 @@
ArrayTypeTrait ATT = ArrayTypeTraitFromTokKind(Tok.getKind());
SourceLocation Loc = ConsumeToken();
- SourceLocation LParen = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return ExprError();
TypeResult Ty = ParseTypeName();
@@ -2353,8 +2376,9 @@
switch (ATT) {
case ATT_ArrayRank: {
- SourceLocation RParen = MatchRHSPunctuation(tok::r_paren, LParen);
- return Actions.ActOnArrayTypeTrait(ATT, Loc, Ty.get(), NULL, RParen);
+ T.consumeClose();
+ return Actions.ActOnArrayTypeTrait(ATT, Loc, Ty.get(), NULL,
+ T.getCloseLocation());
}
case ATT_ArrayExtent: {
if (ExpectAndConsume(tok::comma, diag::err_expected_comma)) {
@@ -2363,9 +2387,10 @@
}
ExprResult DimExpr = ParseExpression();
- SourceLocation RParen = MatchRHSPunctuation(tok::r_paren, LParen);
+ T.consumeClose();
- return Actions.ActOnArrayTypeTrait(ATT, Loc, Ty.get(), DimExpr.get(), RParen);
+ return Actions.ActOnArrayTypeTrait(ATT, Loc, Ty.get(), DimExpr.get(),
+ T.getCloseLocation());
}
default:
break;
@@ -2383,15 +2408,16 @@
ExpressionTrait ET = ExpressionTraitFromTokKind(Tok.getKind());
SourceLocation Loc = ConsumeToken();
- SourceLocation LParen = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return ExprError();
ExprResult Expr = ParseExpression();
- SourceLocation RParen = MatchRHSPunctuation(tok::r_paren, LParen);
+ T.consumeClose();
- return Actions.ActOnExpressionTrait(ET, Loc, Expr.get(), RParen);
+ return Actions.ActOnExpressionTrait(ET, Loc, Expr.get(),
+ T.getCloseLocation());
}
@@ -2401,8 +2427,7 @@
ExprResult
Parser::ParseCXXAmbiguousParenExpression(ParenParseOption &ExprType,
ParsedType &CastTy,
- SourceLocation LParenLoc,
- SourceLocation &RParenLoc) {
+ BalancedDelimiterTracker &Tracker) {
assert(getLang().CPlusPlus && "Should only be called for C++!");
assert(ExprType == CastExpr && "Compound literals are not ambiguous!");
assert(isTypeIdInParens() && "Not a type-id!");
@@ -2436,7 +2461,7 @@
// the context that follows them.
if (!ConsumeAndStoreUntil(tok::r_paren, Toks)) {
// We didn't find the ')' we expected.
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ Tracker.consumeClose();
return ExprError();
}
@@ -2481,15 +2506,14 @@
ParseDeclarator(DeclaratorInfo);
// Match the ')'.
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ Tracker.consumeClose();
if (ParseAs == CompoundLiteral) {
ExprType = CompoundLiteral;
TypeResult Ty = ParseTypeName();
- return ParseCompoundLiteralExpression(Ty.get(), LParenLoc, RParenLoc);
+ return ParseCompoundLiteralExpression(Ty.get(),
+ Tracker.getOpenLocation(),
+ Tracker.getCloseLocation());
}
// We parsed '(' type-id ')' and the thing after it wasn't a '{'.
@@ -2500,9 +2524,9 @@
// Result is what ParseCastExpression returned earlier.
if (!Result.isInvalid())
- Result = Actions.ActOnCastExpr(getCurScope(), LParenLoc,
- DeclaratorInfo, CastTy,
- RParenLoc, Result.take());
+ Result = Actions.ActOnCastExpr(getCurScope(), Tracker.getOpenLocation(),
+ DeclaratorInfo, CastTy,
+ Tracker.getCloseLocation(), Result.take());
return move(Result);
}
@@ -2512,7 +2536,8 @@
ExprType = SimpleExpr;
Result = ParseExpression();
if (!Result.isInvalid() && Tok.is(tok::r_paren))
- Result = Actions.ActOnParenExpr(LParenLoc, Tok.getLocation(), Result.take());
+ Result = Actions.ActOnParenExpr(Tracker.getOpenLocation(),
+ Tok.getLocation(), Result.take());
// Match the ')'.
if (Result.isInvalid()) {
@@ -2520,10 +2545,6 @@
return ExprError();
}
- if (Tok.is(tok::r_paren))
- RParenLoc = ConsumeParen();
- else
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
-
+ Tracker.consumeClose();
return move(Result);
}
diff --git a/lib/Parse/ParseInit.cpp b/lib/Parse/ParseInit.cpp
index ad7bcb2..33abc93 100644
--- a/lib/Parse/ParseInit.cpp
+++ b/lib/Parse/ParseInit.cpp
@@ -139,7 +139,10 @@
//
InMessageExpressionRAIIObject InMessage(*this, true);
- SourceLocation StartLoc = ConsumeBracket();
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
+ SourceLocation StartLoc = T.getOpenLocation();
+
ExprResult Idx;
// If Objective-C is enabled and this is a typename (class message
@@ -266,8 +269,9 @@
StartLoc, EllipsisLoc));
}
- SourceLocation EndLoc = MatchRHSPunctuation(tok::r_square, StartLoc);
- Desig.getDesignator(Desig.getNumDesignators() - 1).setRBracketLoc(EndLoc);
+ T.consumeClose();
+ Desig.getDesignator(Desig.getNumDesignators() - 1).setRBracketLoc(
+ T.getCloseLocation());
}
// Okay, we're done with the designator sequence. We know that there must be
@@ -316,7 +320,9 @@
ExprResult Parser::ParseBraceInitializer() {
InMessageExpressionRAIIObject InMessage(*this, false);
- SourceLocation LBraceLoc = ConsumeBrace();
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ T.consumeOpen();
+ SourceLocation LBraceLoc = T.getOpenLocation();
/// InitExprs - This is the actual list of expressions contained in the
/// initializer.
@@ -376,12 +382,13 @@
// Handle trailing comma.
if (Tok.is(tok::r_brace)) break;
}
- if (InitExprsOk && Tok.is(tok::r_brace))
- return Actions.ActOnInitList(LBraceLoc, move_arg(InitExprs),
- ConsumeBrace());
- // Match the '}'.
- MatchRHSPunctuation(tok::r_brace, LBraceLoc);
+ bool closed = !T.consumeClose();
+
+ if (InitExprsOk && closed)
+ return Actions.ActOnInitList(LBraceLoc, move_arg(InitExprs),
+ T.getCloseLocation());
+
return ExprError(); // an error occurred.
}
diff --git a/lib/Parse/ParseObjc.cpp b/lib/Parse/ParseObjc.cpp
index 78c6b87..88044d1 100644
--- a/lib/Parse/ParseObjc.cpp
+++ b/lib/Parse/ParseObjc.cpp
@@ -164,8 +164,11 @@
SourceLocation nameLoc = ConsumeToken();
if (Tok.is(tok::l_paren) &&
!isKnownToBeTypeSpecifier(GetLookAheadToken(1))) { // we have a category.
- SourceLocation LParenLoc = ConsumeParen();
- SourceLocation categoryLoc, rparenLoc;
+
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
+ SourceLocation categoryLoc;
IdentifierInfo *categoryId = 0;
if (Tok.is(tok::code_completion)) {
Actions.CodeCompleteObjCInterfaceCategory(getCurScope(), nameId, nameLoc);
@@ -182,9 +185,9 @@
Diag(Tok, diag::err_expected_ident); // missing category name.
return 0;
}
-
- rparenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
- if (rparenLoc.isInvalid())
+
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return 0;
if (!attrs.empty()) { // categories don't support attributes.
@@ -497,7 +500,8 @@
///
void Parser::ParseObjCPropertyAttribute(ObjCDeclSpec &DS) {
assert(Tok.getKind() == tok::l_paren);
- SourceLocation LHSLoc = ConsumeParen(); // consume '('
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
while (1) {
if (Tok.is(tok::code_completion)) {
@@ -508,7 +512,7 @@
// If this is not an identifier at all, bail out early.
if (II == 0) {
- MatchRHSPunctuation(tok::r_paren, LHSLoc);
+ T.consumeClose();
return;
}
@@ -587,7 +591,7 @@
ConsumeToken();
}
- MatchRHSPunctuation(tok::r_paren, LHSLoc);
+ T.consumeClose();
}
/// objc-method-proto:
@@ -828,7 +832,9 @@
assert(Tok.is(tok::l_paren) && "expected (");
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
SourceLocation TypeStartLoc = Tok.getLocation();
ObjCDeclContextSwitch ObjCDC(*this);
@@ -867,7 +873,7 @@
}
if (Tok.is(tok::r_paren))
- ConsumeParen();
+ T.consumeClose();
else if (Tok.getLocation() == TypeStartLoc) {
// If we didn't eat any tokens, then this isn't a type.
Diag(Tok, diag::err_expected_type);
@@ -875,7 +881,7 @@
} else {
// Otherwise, we found *something*, but didn't get a ')' in the right
// place. Emit an error then return what we have as the type.
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
}
return Ty;
}
@@ -1196,7 +1202,8 @@
ParseScope ClassScope(this, Scope::DeclScope|Scope::ClassScope);
ObjCDeclContextSwitch ObjCDC(*this);
- SourceLocation LBraceLoc = ConsumeBrace(); // the "{"
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ T.consumeOpen();
// While we still have something to read, read the instance variables.
while (Tok.isNot(tok::r_brace) && Tok.isNot(tok::eof)) {
@@ -1276,15 +1283,16 @@
SkipUntil(tok::r_brace, true, true);
}
}
- SourceLocation RBraceLoc = MatchRHSPunctuation(tok::r_brace, LBraceLoc);
+ T.consumeClose();
+
Actions.ActOnObjCContainerStartDefinition(interfaceDecl);
- Actions.ActOnLastBitfield(RBraceLoc, AllIvarDecls);
+ Actions.ActOnLastBitfield(T.getCloseLocation(), AllIvarDecls);
Actions.ActOnObjCContainerFinishDefinition();
// Call ActOnFields() even if we don't have any decls. This is useful
// for code rewriting tools that need to be aware of the empty list.
Actions.ActOnFields(getCurScope(), atLoc, interfaceDecl,
AllIvarDecls,
- LBraceLoc, RBraceLoc, 0);
+ T.getOpenLocation(), T.getCloseLocation(), 0);
return;
}
@@ -2407,17 +2415,19 @@
if (Tok.isNot(tok::l_paren))
return ExprError(Diag(Tok, diag::err_expected_lparen_after) << "@encode");
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
TypeResult Ty = ParseTypeName();
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
if (Ty.isInvalid())
return ExprError();
- return Owned(Actions.ParseObjCEncodeExpression(AtLoc, EncLoc, LParenLoc,
- Ty.get(), RParenLoc));
+ return Owned(Actions.ParseObjCEncodeExpression(AtLoc, EncLoc,
+ T.getOpenLocation(), Ty.get(),
+ T.getCloseLocation()));
}
/// objc-protocol-expression
@@ -2429,7 +2439,8 @@
if (Tok.isNot(tok::l_paren))
return ExprError(Diag(Tok, diag::err_expected_lparen_after) << "@protocol");
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
if (Tok.isNot(tok::identifier))
return ExprError(Diag(Tok, diag::err_expected_ident));
@@ -2437,10 +2448,11 @@
IdentifierInfo *protocolId = Tok.getIdentifierInfo();
ConsumeToken();
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
return Owned(Actions.ParseObjCProtocolExpression(protocolId, AtLoc, ProtoLoc,
- LParenLoc, RParenLoc));
+ T.getOpenLocation(),
+ T.getCloseLocation()));
}
/// objc-selector-expression
@@ -2452,9 +2464,11 @@
return ExprError(Diag(Tok, diag::err_expected_lparen_after) << "@selector");
SmallVector<IdentifierInfo *, 12> KeyIdents;
- SourceLocation LParenLoc = ConsumeParen();
SourceLocation sLoc;
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
if (Tok.is(tok::code_completion)) {
Actions.CodeCompleteObjCSelector(getCurScope(), KeyIdents.data(),
KeyIdents.size());
@@ -2497,10 +2511,11 @@
break;
}
}
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
Selector Sel = PP.getSelectorTable().getSelector(nColons, &KeyIdents[0]);
return Owned(Actions.ParseObjCSelectorExpression(Sel, AtLoc, SelectorLoc,
- LParenLoc, RParenLoc));
+ T.getOpenLocation(),
+ T.getCloseLocation()));
}
Decl *Parser::ParseLexedObjCMethodDefs(LexedMethod &LM) {
diff --git a/lib/Parse/ParseStmt.cpp b/lib/Parse/ParseStmt.cpp
index 22a1eb3..a2b7cdd 100644
--- a/lib/Parse/ParseStmt.cpp
+++ b/lib/Parse/ParseStmt.cpp
@@ -708,8 +708,9 @@
Tok.getLocation(),
"in compound statement ('{}')");
InMessageExpressionRAIIObject InMessage(*this, false);
-
- SourceLocation LBraceLoc = ConsumeBrace(); // eat the '{'.
+ BalancedDelimiterTracker T(*this, tok::l_brace);
+ if (T.consumeOpen())
+ return StmtError();
StmtVector Stmts(Actions);
@@ -807,13 +808,15 @@
// We broke out of the while loop because we found a '}' or EOF.
if (Tok.isNot(tok::r_brace)) {
Diag(Tok, diag::err_expected_rbrace);
- Diag(LBraceLoc, diag::note_matching) << "{";
+ Diag(T.getOpenLocation(), diag::note_matching) << "{";
return StmtError();
}
- SourceLocation RBraceLoc = ConsumeBrace();
- return Actions.ActOnCompoundStmt(LBraceLoc, RBraceLoc, move_arg(Stmts),
- isStmtExpr);
+ if (T.consumeClose())
+ return StmtError();
+
+ return Actions.ActOnCompoundStmt(T.getOpenLocation(), T.getCloseLocation(),
+ move_arg(Stmts), isStmtExpr);
}
/// ParseParenExprOrCondition:
@@ -831,7 +834,9 @@
Decl *&DeclResult,
SourceLocation Loc,
bool ConvertToBoolean) {
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
if (getLang().CPlusPlus)
ParseCXXCondition(ExprResult, DeclResult, Loc, ConvertToBoolean);
else {
@@ -856,7 +861,7 @@
}
// Otherwise the condition is valid or the rparen is present.
- MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
return false;
}
@@ -1204,16 +1209,17 @@
}
// Parse the parenthesized condition.
- SourceLocation LPLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
ExprResult Cond = ParseExpression();
- SourceLocation RPLoc = MatchRHSPunctuation(tok::r_paren, LPLoc);
+ T.consumeClose();
DoScope.Exit();
if (Cond.isInvalid() || Body.isInvalid())
return StmtError();
- return Actions.ActOnDoStmt(DoLoc, Body.get(), WhileLoc, LPLoc,
- Cond.get(), RPLoc);
+ return Actions.ActOnDoStmt(DoLoc, Body.get(), WhileLoc, T.getOpenLocation(),
+ Cond.get(), T.getCloseLocation());
}
/// ParseForStatement
@@ -1273,7 +1279,9 @@
ParseScope ForScope(this, ScopeFlags);
- SourceLocation LParenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
+
ExprResult Value;
bool ForEach = false, ForRange = false;
@@ -1413,18 +1421,18 @@
}
}
// Match the ')'.
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, LParenLoc);
+ T.consumeClose();
// We need to perform most of the semantic analysis for a C++0x for-range
// statememt before parsing the body, in order to be able to deduce the type
// of an auto-typed loop variable.
StmtResult ForRangeStmt;
if (ForRange) {
- ForRangeStmt = Actions.ActOnCXXForRangeStmt(ForLoc, LParenLoc,
+ ForRangeStmt = Actions.ActOnCXXForRangeStmt(ForLoc, T.getOpenLocation(),
FirstPart.take(),
ForRangeInit.ColonLoc,
ForRangeInit.RangeExpr.get(),
- RParenLoc);
+ T.getCloseLocation());
// Similarly, we need to do the semantic analysis for a for-range
@@ -1462,16 +1470,18 @@
return StmtError();
if (ForEach)
- return Actions.ActOnObjCForCollectionStmt(ForLoc, LParenLoc,
- FirstPart.take(),
- Collection.take(), RParenLoc,
- Body.take());
+ return Actions.ActOnObjCForCollectionStmt(ForLoc, T.getOpenLocation(),
+ FirstPart.take(),
+ Collection.take(),
+ T.getCloseLocation(),
+ Body.take());
if (ForRange)
return Actions.FinishCXXForRangeStmt(ForRangeStmt.take(), Body.take());
- return Actions.ActOnForStmt(ForLoc, LParenLoc, FirstPart.take(), SecondPart,
- SecondVar, ThirdPart, RParenLoc, Body.take());
+ return Actions.ActOnForStmt(ForLoc, T.getOpenLocation(), FirstPart.take(),
+ SecondPart, SecondVar, ThirdPart,
+ T.getCloseLocation(), Body.take());
}
/// ParseGotoStatement
@@ -1742,7 +1752,8 @@
SkipUntil(tok::r_paren);
return StmtError();
}
- Loc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
ExprResult AsmString(ParseAsmStringLiteral());
if (AsmString.isInvalid())
@@ -1755,12 +1766,12 @@
if (Tok.is(tok::r_paren)) {
// We have a simple asm expression like 'asm("foo")'.
- SourceLocation RParenLoc = ConsumeParen();
+ T.consumeClose();
return Actions.ActOnAsmStmt(AsmLoc, /*isSimple*/ true, isVolatile,
/*NumOutputs*/ 0, /*NumInputs*/ 0, 0,
move_arg(Constraints), move_arg(Exprs),
AsmString.take(), move_arg(Clobbers),
- RParenLoc);
+ T.getCloseLocation());
}
// Parse Outputs, if present.
@@ -1820,12 +1831,12 @@
}
}
- SourceLocation RParenLoc = MatchRHSPunctuation(tok::r_paren, Loc);
+ T.consumeClose();
return Actions.ActOnAsmStmt(AsmLoc, false, isVolatile,
NumOutputs, NumInputs, Names.data(),
move_arg(Constraints), move_arg(Exprs),
AsmString.take(), move_arg(Clobbers),
- RParenLoc);
+ T.getCloseLocation());
}
/// ParseAsmOperands - Parse the asm-operands production as used by
@@ -1851,7 +1862,8 @@
while (1) {
// Read the [id] if present.
if (Tok.is(tok::l_square)) {
- SourceLocation Loc = ConsumeBracket();
+ BalancedDelimiterTracker T(*this, tok::l_square);
+ T.consumeOpen();
if (Tok.isNot(tok::identifier)) {
Diag(Tok, diag::err_expected_ident);
@@ -1863,7 +1875,7 @@
ConsumeToken();
Names.push_back(II);
- MatchRHSPunctuation(tok::r_square, Loc);
+ T.consumeClose();
} else
Names.push_back(0);
@@ -1881,9 +1893,10 @@
}
// Read the parenthesized expression.
- SourceLocation OpenLoc = ConsumeParen();
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ T.consumeOpen();
ExprResult Res(ParseExpression());
- MatchRHSPunctuation(tok::r_paren, OpenLoc);
+ T.consumeClose();
if (Res.isInvalid()) {
SkipUntil(tok::r_paren);
return true;
@@ -2078,8 +2091,8 @@
SourceLocation CatchLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
- if (ExpectAndConsume(tok::l_paren, diag::err_expected_lparen))
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.expectAndConsume(diag::err_expected_lparen))
return StmtError();
// C++ 3.3.2p3:
@@ -2100,7 +2113,8 @@
} else
ConsumeToken();
- if (MatchRHSPunctuation(tok::r_paren, LParenLoc).isInvalid())
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return StmtError();
if (Tok.isNot(tok::l_brace))
diff --git a/lib/Parse/Parser.cpp b/lib/Parse/Parser.cpp
index 05a2b15..c909643 100644
--- a/lib/Parse/Parser.cpp
+++ b/lib/Parse/Parser.cpp
@@ -122,34 +122,6 @@
<< FixItHint::CreateInsertion(EndLoc, ")");
}
-/// MatchRHSPunctuation - For punctuation with a LHS and RHS (e.g. '['/']'),
-/// this helper function matches and consumes the specified RHS token if
-/// present. If not present, it emits a corresponding diagnostic indicating
-/// that the parser failed to match the RHS of the token at LHSLoc.
-SourceLocation Parser::MatchRHSPunctuation(tok::TokenKind RHSTok,
- SourceLocation LHSLoc) {
-
- if (Tok.is(RHSTok))
- return ConsumeAnyToken();
-
- SourceLocation R = Tok.getLocation();
- const char *LHSName = "unknown";
- diag::kind DID = diag::err_parse_error;
- switch (RHSTok) {
- default: break;
- case tok::r_paren : LHSName = "("; DID = diag::err_expected_rparen; break;
- case tok::r_brace : LHSName = "{"; DID = diag::err_expected_rbrace; break;
- case tok::r_square: LHSName = "["; DID = diag::err_expected_rsquare; break;
- case tok::greater: LHSName = "<"; DID = diag::err_expected_greater; break;
- case tok::greatergreatergreater:
- LHSName = "<<<"; DID = diag::err_expected_ggg; break;
- }
- Diag(Tok, DID);
- Diag(LHSLoc, diag::note_matching) << LHSName;
- SkipUntil(RHSTok);
- return R;
-}
-
static bool IsCommonTypo(tok::TokenKind ExpectedTok, const Token &Tok) {
switch (ExpectedTok) {
case tok::semi: return Tok.is(tok::colon); // : for ;
@@ -1147,13 +1119,12 @@
ConsumeToken();
}
- if (Tok.isNot(tok::l_paren)) {
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.consumeOpen()) {
Diag(Tok, diag::err_expected_lparen_after) << "asm";
return ExprError();
}
- Loc = ConsumeParen();
-
ExprResult Result(ParseAsmStringLiteral());
if (Result.isInvalid()) {
@@ -1162,9 +1133,10 @@
*EndLoc = Tok.getLocation();
ConsumeAnyToken();
} else {
- Loc = MatchRHSPunctuation(tok::r_paren, Loc);
+ // Close the paren and get the location of the end bracket
+ T.consumeClose();
if (EndLoc)
- *EndLoc = Loc;
+ *EndLoc = T.getCloseLocation();
}
return move(Result);
@@ -1489,13 +1461,12 @@
Token Condition = Tok;
SourceLocation IfExistsLoc = ConsumeToken();
- SourceLocation LParenLoc = Tok.getLocation();
- if (Tok.isNot(tok::l_paren)) {
+ BalancedDelimiterTracker T(*this, tok::l_paren);
+ if (T.consumeOpen()) {
Diag(Tok, diag::err_expected_lparen_after) << IfExistsLoc;
SkipUntil(tok::semi);
return true;
}
- ConsumeParen(); // eat the '('.
// Parse nested-name-specifier.
CXXScopeSpec SS;
@@ -1514,7 +1485,8 @@
return true;
}
- if (MatchRHSPunctuation(tok::r_paren, LParenLoc).isInvalid())
+ T.consumeClose();
+ if (T.getCloseLocation().isInvalid())
return true;
// Check if the symbol exists.
@@ -1581,3 +1553,64 @@
return Actions.ConvertDeclToDeclGroup(Import.get());
}
+
+bool Parser::BalancedDelimiterTracker::consumeOpen() {
+ // Try to consume the token we are holding
+ if (P.Tok.is(Kind)) {
+ P.QuantityTracker.push(Kind);
+ Cleanup = true;
+ if (P.QuantityTracker.getDepth(Kind) < MaxDepth) {
+ LOpen = P.ConsumeAnyToken();
+ return false;
+ } else {
+ P.Diag(P.Tok, diag::err_parser_impl_limit_overflow);
+ P.SkipUntil(tok::eof);
+ }
+ }
+ return true;
+}
+
+bool Parser::BalancedDelimiterTracker::expectAndConsume(unsigned DiagID,
+ const char *Msg,
+ tok::TokenKind SkipToToc ) {
+ LOpen = P.Tok.getLocation();
+ if (!P.ExpectAndConsume(Kind, DiagID, Msg, SkipToToc)) {
+ P.QuantityTracker.push(Kind);
+ Cleanup = true;
+ if (P.QuantityTracker.getDepth(Kind) < MaxDepth) {
+ return false;
+ } else {
+ P.Diag(P.Tok, diag::err_parser_impl_limit_overflow);
+ P.SkipUntil(tok::eof);
+ }
+ }
+ return true;
+}
+
+bool Parser::BalancedDelimiterTracker::consumeClose() {
+ if (P.Tok.is(Close)) {
+ LClose = P.ConsumeAnyToken();
+ if (Cleanup)
+ P.QuantityTracker.pop(Kind);
+
+ Cleanup = false;
+ return false;
+ } else {
+ const char *LHSName = "unknown";
+ diag::kind DID = diag::err_parse_error;
+ switch (Close) {
+ default: break;
+ case tok::r_paren : LHSName = "("; DID = diag::err_expected_rparen; break;
+ case tok::r_brace : LHSName = "{"; DID = diag::err_expected_rbrace; break;
+ case tok::r_square: LHSName = "["; DID = diag::err_expected_rsquare; break;
+ case tok::greater: LHSName = "<"; DID = diag::err_expected_greater; break;
+ case tok::greatergreatergreater:
+ LHSName = "<<<"; DID = diag::err_expected_ggg; break;
+ }
+ P.Diag(P.Tok, DID);
+ P.Diag(LOpen, diag::note_matching) << LHSName;
+ if (P.SkipUntil(Close))
+ LClose = P.Tok.getLocation();
+ }
+ return true;
+}
diff --git a/test/Parser/parser_overflow.c b/test/Parser/parser_overflow.c
new file mode 100644
index 0000000..d2006ea
--- /dev/null
+++ b/test/Parser/parser_overflow.c
@@ -0,0 +1,7 @@
+// RUN: %clang_cc1 %s -fsyntax-only 2>&1 | FileCheck %s
+
+void foo(void) {
+ {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
+}
+
+// CHECK: fatal error: parser recursion limit reached, program too complex