[pseudo] Fix an out-of-bound error in LRTable::find.

[hokein]

Summary

The linear scan should not escape the TargetedStates range.

[sammccall]

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

114–115

I think this check is no longer needed

[aaron.ballman]

I'm seeing debug failures again on Windows after this.

FAIL: Clang :: Syntax/lr-build-conflicts.test (14728 of 14729)
******************** TEST 'Clang :: Syntax/lr-build-conflicts.test' FAILED ********************
Script:
--
: 'RUN: at line 5';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test -print-graph | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test --check-prefix=GRAPH
: 'RUN: at line 30';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test -print-table | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test --check-prefix=TABLE
--
Exit Code: 2

Command Output (stdout):
--
$ ":" "RUN: at line 5"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "-print-graph"
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "--check-prefix=GRAPH"
$ ":" "RUN: at line 30"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "-print-table"
note: command had no output on stdout or stderr
error: command failed with exit status: 3221226505
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "--check-prefix=TABLE"
# command stderr:
FileCheck error: '<stdin>' is empty.
FileCheck command line:  f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test --check-prefix=TABLE

error: command failed with exit status: 2

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
FAIL: Clang :: Syntax/lr-build-basic.test (14729 of 14729)
******************** TEST 'Clang :: Syntax/lr-build-basic.test' FAILED ********************
Script:
--
: 'RUN: at line 5';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test -print-graph | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test --check-prefix=GRAPH
: 'RUN: at line 18';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test -print-table | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test --check-prefix=TABLE
--
Exit Code: 2

Command Output (stdout):
--
$ ":" "RUN: at line 5"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "-print-graph"
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "--check-prefix=GRAPH"
$ ":" "RUN: at line 18"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "-print-table"
note: command had no output on stdout or stderr
error: command failed with exit status: 3221226505
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "--check-prefix=TABLE"
# command stderr:
FileCheck error: '<stdin>' is empty.
FileCheck command line:  f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test --check-prefix=TABLE

error: command failed with exit status: 2

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
********************
Failed Tests (2):
  Clang :: Syntax/lr-build-basic.test
  Clang :: Syntax/lr-build-conflicts.test


Testing Time: 336.94s
  Unsupported      :  1727
  Passed           : 12972
  Expectedly Failed:    28
  Failed           :     2

It looks to be another index out of bounds assert with the MSVC STL debug iterators. Can you fix or revert?

[hokein]

In D120723#3356831, @aaron.ballman wrote:

I'm seeing debug failures again on Windows after this.

FAIL: Clang :: Syntax/lr-build-conflicts.test (14728 of 14729)
******************** TEST 'Clang :: Syntax/lr-build-conflicts.test' FAILED ********************
Script:
--
: 'RUN: at line 5';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test -print-graph | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test --check-prefix=GRAPH
: 'RUN: at line 30';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test -print-table | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test --check-prefix=TABLE
--
Exit Code: 2

Command Output (stdout):
--
$ ":" "RUN: at line 5"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "-print-graph"
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "--check-prefix=GRAPH"
$ ":" "RUN: at line 30"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "-print-table"
note: command had no output on stdout or stderr
error: command failed with exit status: 3221226505
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test" "--check-prefix=TABLE"
# command stderr:
FileCheck error: '<stdin>' is empty.
FileCheck command line:  f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-conflicts.test --check-prefix=TABLE

error: command failed with exit status: 2

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
FAIL: Clang :: Syntax/lr-build-basic.test (14729 of 14729)
******************** TEST 'Clang :: Syntax/lr-build-basic.test' FAILED ********************
Script:
--
: 'RUN: at line 5';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test -print-graph | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test --check-prefix=GRAPH
: 'RUN: at line 18';   clang-pseudo -grammar F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test -print-table | f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test --check-prefix=TABLE
--
Exit Code: 2

Command Output (stdout):
--
$ ":" "RUN: at line 5"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "-print-graph"
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "--check-prefix=GRAPH"
$ ":" "RUN: at line 18"
$ "clang-pseudo" "-grammar" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "-print-table"
note: command had no output on stdout or stderr
error: command failed with exit status: 3221226505
$ "f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe" "F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test" "--check-prefix=TABLE"
# command stderr:
FileCheck error: '<stdin>' is empty.
FileCheck command line:  f:\source\llvm-project\llvm\out\build\x64-debug\bin\filecheck.exe F:\source\llvm-project\clang\test\Syntax\lr-build-basic.test --check-prefix=TABLE

error: command failed with exit status: 2

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
********************
Failed Tests (2):
  Clang :: Syntax/lr-build-basic.test
  Clang :: Syntax/lr-build-conflicts.test


Testing Time: 336.94s
  Unsupported      :  1727
  Passed           : 12972
  Expectedly Failed:    28
  Failed           :     2

It looks to be another index out of bounds assert with the MSVC STL debug iterators. Can you fix or revert?

oops.. sorry. Looking at it now.

[hokein]

Fixed in 28ccf326725d0fea8648834c8acdbdfe3aa40d7a.

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

114–115

sorry, should have thought more carefully on this comment, we need this check to make sure we don't access Actions[Actions.end()] on Line120 below.

[aaron.ballman]

In D120723#3356925, @hokein wrote:

Fixed in 28ccf326725d0fea8648834c8acdbdfe3aa40d7a.

Thanks! I can confirm this is fixed on my end now.

[sammccall]

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

114–115

Sorry about that.

You're right, we formally do &*Actions[Actions.size()], which is invalid.

However we don't actually need a runtime check, just a change of syntax to avoid the dereference:

return llvm::makeArrayRef(Actions.data() + (Start - States.data()), End - Start);

clang/lib/Tooling/Syntax/Pseudo/LRTable.cpp

std::pair<size_t, size_t> TargetStateRange =
       isToken(ID) ? std::make_pair(TerminalOffset[Idx], TerminalOffset[Idx + 1])
                   : std::make_pair(NontermOffset[Idx], NontermOffset[Idx + 1]);
   auto TargetedStates =
       llvm::makeArrayRef(States.data() + TargetStateRange.first,
                          States.data() + TargetStateRange.second);
 
   assert(llvm::is_sorted(TargetedStates) &&
          "subrange of the StateIdx should be sorted!");
-  const LRTable::StateID *It = llvm::partition_point(
+  const LRTable::StateID *Start = llvm::partition_point(
       TargetedStates, [&Src](LRTable::StateID S) { return S < Src; });
-  if (It == TargetedStates.end())
-    return {};
-  size_t Start = It - States.data(), End = Start;
-  while (End < States.size() && States[End] == Src)
+  const LRTable::StateID *End = Start;
+  while (End != TargetedStates.end() && *End == Src)
     ++End;
-  return llvm::makeArrayRef(&Actions[Start], End - Start);
+  return llvm::makeArrayRef(&Actions[Start - States.data()],
+                            /*length=*/End - Start);
 }
 
 } // namespace pseudo
 } // namespace syntax
 } // namespace clang

clang/test/Syntax/lr-build-basic.test

 _ := expr
-expr := IDENTIFIER
+expr := id
+id := IDENTIFIER
 
 # RUN: clang-pseudo -grammar %s -print-graph | FileCheck %s --check-prefix=GRAPH
 #      GRAPH: States:
 # GRPAH-NEXT: State 0
 # GRPAH-NEXT:     _ :=  • expr
-# GRPAH-NEXT:     expr :=  • IDENTIFIER
+# GRPAH-NEXT:     expr :=  • id
+# GRPAH-NEXT:     id :=  • IDENTIFIER
 # GRPAH-NEXT: State 1
 # GRPAH-NEXT:     _ := expr • 
 # GRPAH-NEXT: State 2
-# GRPAH-NEXT:     expr := IDENTIFIER • 
-# GRPAH-NEXT: 0 ->[expr] 1
-# GRPAH-NEXT: 0 ->[IDENTIFIER] 2
+# GRPAH-NEXT:     expr := id • 
+# GRPAH-NEXT: State 3
+# GRPAH-NEXT:     id := IDENTIFIER • 
 
 # RUN: clang-pseudo -grammar %s -print-table | FileCheck %s --check-prefix=TABLE
 #      TABLE: LRTable:
 # TABLE-NEXT: State 0
-# TABLE-NEXT:     'IDENTIFIER': shift state 2
+# TABLE-NEXT:     'IDENTIFIER': shift state 3
 # TABLE-NEXT:     'expr': go to state 1
+# TABLE-NEXT:     'id': go to state 2
 # TABLE-NEXT: State 1
 # TABLE-NEXT:     'EOF': accept
 # TABLE-NEXT: State 2
-# TABLE-NEXT:     'EOF': reduce by rule 1 'expr := IDENTIFIER'
+# TABLE-NEXT:     'EOF': reduce by rule 1 'expr := id'
+# TABLE-NEXT: State 3
+# TABLE-NEXT:     'EOF': reduce by rule 2 'id := IDENTIFIER'