C++ crashes on new test ParserExec/ListLabelsOnRuleRefStartOfAlt.txt

[parrt]

Looks like there's an issue in ArrayPredictionContext::equals() exposed by this test from this Test.cpp line:

  tree::ParseTree *tree = parser.expression();

Run

$ cd ~/antlr/code/antlr4/runtime/Cpp
$ cmake . -DTRACE_ATN=ON -DCMAKE_BUILD_TYPE=Debug

Then from test dir we get :

$ cat input
a and b
$ ln -s /Users/parrt/antlr/code/antlr4/runtime/Cpp/dist/libantlr4-runtime.dylib 
$ clang++ -g -std=c++17 -I /Users/parrt/antlr/code/antlr4/runtime/Cpp/runtime/src -L. -lantlr4-runtime *.cpp
$ ./a.out input
Segmentation fault: 11

and see from lldb (with Debug mode for cmake build of lib):

* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x00000001013167e4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::operator==(lhs=0x0000000000000000, rhs=0x0000000000000000) at PredictionContext.h:206:16
   203 	  };
   204 	
   205 	  inline bool operator==(const PredictionContext &lhs, const PredictionContext &rhs) {
-> 206 	    return lhs.equals(rhs);
   207 	  }
   208 	
   209 	  inline bool operator!=(const PredictionContext &lhs, const PredictionContext &rhs) {

and trace:

* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x00000001013167e4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::operator==(lhs=0x0000000000000000, rhs=0x0000000000000000) at PredictionContext.h:206:16
    frame #1: 0x0000000101346c10 libantlr4-runtime.4.10.1.dylib`(anonymous namespace)::predictionContextEqual(lhs=nullptr, rhs=nullptr) at ArrayPredictionContext.cpp:25:17
    frame #2: 0x0000000101346b80 libantlr4-runtime.4.10.1.dylib`bool std::__1::equal<std::__1::__wrap_iter<std::__1::shared_ptr<antlr4::atn::PredictionContext const> const*>, std::__1::__wrap_iter<std::__1::shared_ptr<antlr4::atn::PredictionContext const> const*>, bool (*)(std::__1::shared_ptr<antlr4::atn::PredictionContext const> const&, std::__1::shared_ptr<antlr4::atn::PredictionContext const> const&)>(__first1=__wrap_iter<const std::__1::shared_ptr<const antlr4::atn::PredictionContext> *> @ 0x000000016fdfb6a0, __last1=__wrap_iter<const std::__1::shared_ptr<const antlr4::atn::PredictionContext> *> @ 0x000000016fdfb698, __first2=__wrap_iter<const std::__1::shared_ptr<const antlr4::atn::PredictionContext> *> @ 0x000000016fdfb690, __pred=(libantlr4-runtime.4.10.1.dylib`(anonymous namespace)::predictionContextEqual(std::__1::shared_ptr<antlr4::atn::PredictionContext const> const&, std::__1::shared_ptr<antlr4::atn::PredictionContext const> const&) at ArrayPredictionContext.cpp:24))(std::__1::shared_ptr<antlr4::atn::PredictionContext const> const&, std::__1::shared_ptr<antlr4::atn::PredictionContext const> const&)) at equal.h:31:10
    frame #3: 0x0000000101346994 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ArrayPredictionContext::equals(this=0x000000016fdfba68, other=0x00006000026058d8) const at ArrayPredictionContext.cpp:82:10
    frame #4: 0x00000001013167f0 libantlr4-runtime.4.10.1.dylib`antlr4::atn::operator==(lhs=0x000000016fdfba68, rhs=0x00006000026058d8) at PredictionContext.h:206:16
    frame #5: 0x0000000101395120 libantlr4-runtime.4.10.1.dylib`antlr4::atn::PredictionContext::mergeArrays(a=std::__1::shared_ptr<const antlr4::atn::ArrayPredictionContext>::element_type @ 0x00006000026058d8 strong=4 weak=1, b=std::__1::shared_ptr<const antlr4::atn::ArrayPredictionContext>::element_type @ 0x0000600002605b78 strong=1 weak=1, rootIsWildcard=false, mergeCache=0x0000600003504028) at PredictionContext.cpp:411:9
    frame #6: 0x0000000101393320 libantlr4-runtime.4.10.1.dylib`antlr4::atn::PredictionContext::merge(a=std::__1::shared_ptr<const antlr4::atn::PredictionContext>::element_type @ 0x00006000026058d8 strong=4 weak=1, b=std::__1::shared_ptr<const antlr4::atn::PredictionContext>::element_type @ 0x0000600002104068 strong=45 weak=1, rootIsWildcard=false, mergeCache=0x0000600003504028) at PredictionContext.cpp:210:10
    frame #7: 0x0000000101318564 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ATNConfigSet::add(this=0x0000000100405be0, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605b18 strong=1 weak=1, mergeCache=0x0000600003504028) at ATNConfigSet.cpp:64:41
    frame #8: 0x00000001013799b4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605b18 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:890:14
    frame #9: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605b18 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #10: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605ab8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #11: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605ab8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #12: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605a58 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #13: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605a58 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #14: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x00006000026059f8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #15: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x00006000026059f8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #16: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605998 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #17: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605998 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #18: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605938 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #19: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605938 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #20: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605878 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #21: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605878 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #22: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605818 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #23: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605818 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #24: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x00006000026057b8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #25: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x00006000026057b8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #26: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605638 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #27: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605638 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=-1, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #28: 0x0000000101379734 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605578 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:868:9
    frame #29: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605518 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #30: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605518 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #31: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x00006000026053f8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #32: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x00006000026053f8 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #33: 0x0000000101379e3c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure_(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605218 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:959:7
    frame #34: 0x00000001013797d4 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closureCheckingStopState(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605218 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, depth=0, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:880:3
    frame #35: 0x000000010137939c libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::closure(this=0x0000600003504000, config=std::__1::shared_ptr<antlr4::atn::ATNConfig>::element_type @ 0x0000600002605218 strong=1 weak=1, configs=0x0000000100405be0, closureBusy=size=0, collectPredicates=false, fullCtx=true, treatEofAsEpsilon=false) at ParserATNSimulator.cpp:825:3
    frame #36: 0x00000001013777b8 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::computeReachSet(this=0x0000600003504000, closure_=0x00000001004058e0, t=4, fullCtx=true) at ParserATNSimulator.cpp:523:7
    frame #37: 0x0000000101376dd8 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::execATNWithFullContext(this=0x0000600003504000, dfa=0x00000001004048b0, D=0x00006000029055e0, s0=0x0000000100405460, input=0x000000016fdfece0, startIndex=1, outerContext=0x0000600002c08200) at ParserATNSimulator.cpp:355:13
    frame #38: 0x0000000101375be8 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::execATN(this=0x0000600003504000, dfa=0x00000001004048b0, s0=0x0000600002905570, input=0x000000016fdfece0, startIndex=1, outerContext=0x0000600002c08200) at ParserATNSimulator.cpp:238:20
    frame #39: 0x0000000101374f20 libantlr4-runtime.4.10.1.dylib`antlr4::atn::ParserATNSimulator::adaptivePredict(this=0x0000600003504000, input=0x000000016fdfece0, decision=4, outerContext=0x0000600002c08200) at ParserATNSimulator.cpp:155:16
    frame #40: 0x0000000100009c28 a.out`TestParser::expression(this=0x000000016fdfedb0, precedence=0) at TestParser.cpp:227:54
    frame #41: 0x0000000100009904 a.out`TestParser::expression(this=0x000000016fdfedb0) at TestParser.cpp:179:11
    frame #42: 0x0000000100001758 a.out`main(argc=2, argv=0x000000016fdff148) at Test.cpp:31:34
    frame #43: 0x000000010006908c dyld`start + 520

[parrt]

It appears that there are two NULL pointers coming in here:

Line 24 in ArrayPredictionContext.h:

  bool predictionContextEqual(const Ref<const PredictionContext> &lhs, const Ref<const PredictionContext> &rhs) {
    return *lhs == *rhs;
  }

It looks like ArrayPredictionContext::equals() try to compare a number of things for equality using that function but it's not checking for NULL. As those are references I'm not sure how to check for NULL. Ok, it looks like it is undefined behavior to make a reference to an item so this is somehow making a reference to NULL objects:

line 82: ArrayPredictionContext.cpp:

std::equal(parents.begin(), parents.end(), array.parents.begin(), predictionContextEqual);

[mike-lischke]

Right, null is not expected in predictionContextEqual. It could be changed to do so, but IMO the correct solution is to check if parents is empty, something like:

bool ArrayPredictionContext::equals(const PredictionContext &other) const {//
  if (this == std::addressof(other)) {
    return true;
  }
  if (getContextType() != other.getContextType()) {
    return false;
  }
  const auto &array = downCast<const ArrayPredictionContext&>(other);
  return returnStates.size() == array.returnStates.size() &&
         parents.size() == array.parents.size() &&
         cachedHashCodeEqual(cachedHashCode(), array.cachedHashCode()) &&
         std::memcmp(returnStates.data(), array.returnStates.data(), returnStates.size() * sizeof(decltype(returnStates)::value_type)) == 0 &&
         (parents.size() == 0 || std::equal(parents.begin(), parents.end(), array.parents.begin(), predictionContextEqual));
}

Also, splitting this large set of tests into individual lines would increase readability significantly.

[parrt]

Well, I've simplified and am running into limits of my C++.

bool ArrayPredictionContext::equals(const PredictionContext &other) const {
  if (this == std::addressof(other)) {
    return true;
  }
  if (getContextType() != other.getContextType()) {
    return false;
  }
  const auto &array = downCast<const ArrayPredictionContext&>(other);
  const bool sameSize = returnStates.size() == array.returnStates.size() &&
                        parents.size() == array.parents.size();
  const bool sameHash = cachedHashCodeEqual(cachedHashCode(), array.cachedHashCode());
  const size_t stateSizeBytes = sizeof(decltype(returnStates)::value_type);
  const bool stateArraysEqual =
    std::memcmp(returnStates.data(), array.returnStates.data(),
                returnStates.size() * stateSizeBytes) == 0;
  // stack of contexts is the same
  std::cout << parents.size() << "\n"; 
  std::cout << array.parents.size() << "\n";
  const bool parentCtxEqual = std::equal(parents.begin(), parents.end(), array.parents.begin(),  <======= crash
                                         predictionContextEqual);
  return sameSize && sameHash && stateArraysEqual && parentCtxEqual;
}

It prints 2 and then 2 then crashes on that std:equal. I set a breakpoint and get two vectors to compare that look fine minus the nullptr last element:

(lldb) p parents
(std::vector<std::shared_ptr<const antlr4::atn::PredictionContext>, std::allocator<std::shared_ptr<const antlr4::atn::PredictionContext> > >) $2 = size=2 {
  [0] = std::__1::shared_ptr<const antlr4::atn::PredictionContext>::element_type @ 0x0000600002100fb8 strong=41 weak=1 {
    __ptr_ = 0x0000600002100fb8
  }
  [1] = nullptr {
    __ptr_ = nullptr
  }
}
(lldb) p array.parents
(const std::vector<std::shared_ptr<const antlr4::atn::PredictionContext>, std::allocator<std::shared_ptr<const antlr4::atn::PredictionContext> > >) $3 = size=2 {
  [0] = std::__1::shared_ptr<const antlr4::atn::PredictionContext>::element_type @ 0x0000600002100fb8 strong=41 weak=1 {
    __ptr_ = 0x0000600002100fb8
  }
  [1] = nullptr {
    __ptr_ = nullptr
  }
}

We must be pushing a null somewhere as this will try to deref that nullptr:

bool predictionContextEqual(const Ref<const PredictionContext> &lhs, const Ref<const PredictionContext> &rhs) {
    return *lhs == *rhs;
}

[parrt]

My related PR is #3863

[parrt]

I have simplified the grammar. Here is complete test case:

grammar Test;

expression
    : expression (AND expression)+
    | IDENTIFIER
    ;

AND : 'and' ;
IDENTIFIER : [a-zA-Z_]+ ;
WS : [ \t\r\n]+ -> skip ;

Using my antlr4-tools:

$ cd ~/antlr/code/antlr4
$ mvn -DskipTests install
$ cd /tmp/foo # dir with grammar
$ antlr4 -v 4.11-SNAPSHOT -Dlanguage=Cpp *.g4

and Test.cpp:

#include <iostream>

#include "antlr4-runtime.h"
#include "TestLexer.h"
#include "TestParser.h"

using namespace antlr4;

class TreeShapeListener : public tree::ParseTreeListener {
public:
  void visitTerminal(tree::TerminalNode *) override {}
  void visitErrorNode(tree::ErrorNode *) override {}
  void exitEveryRule(ParserRuleContext *) override {}
  void enterEveryRule(ParserRuleContext *ctx) override {
    for (auto child : ctx->children) {
      tree::ParseTree *parent = child->parent;
      ParserRuleContext *rule = dynamic_cast<ParserRuleContext *>(parent);
      if (rule != ctx) {
        throw "Invalid parse tree shape detected.";
      }
    }
  }
};

int main(int argc, const char* argv[]) {
  ANTLRFileStream input;
  input.loadFromFile(argv[1]);
  TestLexer lexer(&input);
  CommonTokenStream tokens(&lexer);
  TestParser parser(&tokens);
  tree::ParseTree *tree = parser.expression();
  TreeShapeListener listener;
  tree::ParseTreeWalker::DEFAULT.walk(&listener, tree);
  return 0;
}

Compile and run:

$ clang++ -g -std=c++17 -I /Users/parrt/antlr/code/antlr4/runtime/Cpp/runtime/src -L/Users/parrt/antlr/code/antlr4/runtime/Cpp/dist -lantlr4-runtime *.cpp
$ lldb ./a.out input
(lldb) target create "./a.out"
Current executable set to '/tmp/foo/a.out' (arm64).
(lldb) settings set -- target.run-args  "input"
(lldb) run
Process 12425 launched: '/tmp/foo/a.out' (arm64)
Process 12425 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x00000001013126f8 libantlr4-runtime.4.10.1.dylib`antlr4::atn::operator==(lhs=0x0000000000000000, rhs=0x0000000000000000) at PredictionContext.h:206:16
   203 	  };
   204 	
   205 	  inline bool operator==(const PredictionContext &lhs, const PredictionContext &rhs) {
-> 206 	    return lhs.equals(rhs);
   207 	  }
   208 	
   209 	  inline bool operator!=(const PredictionContext &lhs, const PredictionContext &rhs) {
Target 0: (a.out) stopped.

[mike-lischke]

I wonder why @jcking doesn't help. It's code from one of his last patches. Wasn't the test not there at that time?

What you see here is that the parents vector has a size != 0, but seems to contain null references (empty shared_ptr). I wonder if that is a valid state (a parent list with null entries). If not then this should be fixed instead of changing ArrayPredictionContext. If it is then we need to fix predictionContextEqual. My suggestion above is nonsense. It checks if the arrays have content, but that's not what causes the trouble (empty arrays do nothing).

  bool predictionContextEqual(const Ref<const PredictionContext> &lhs, const Ref<const PredictionContext> &rhs) {
    // What should happen here? Are lhs and rhs equal if one or both of them are null?
    if (!lhs && !rhs) { 
      return true;
    }

    return *lhs == *rhs;
  }

What if only one is null?

[parrt]

I believe it should NOT have nullptr. There is sometimes a sentinel indicating empty stack but it's a real value and should be compared. (This bug/test is new.)

[parrt]

Improving ATN simulation trace: #3957

More info. Looks like parent element can be null:

public class ArrayPredictionContext extends PredictionContext {
	/** Parent can be null only if full ctx mode and we make an array
	 *  from {@link #EMPTY} and non-empty. We merge {@link #EMPTY} by using null parent and
	 *  returnState == {@link #EMPTY_RETURN_STATE}.
	 */
	public final PredictionContext[] parents;

[parrt]

Fixed by #3958