[TableGen] Add the !substr() bang operator

[Paul-C-Anagnostopoulos]

Summary

This revision adds the !substr bang operator, which, as you might expect, extracts a substring of a string.

I update the documentation and added a test.

I'm not concerned about confusion between !subst and !substr because I plan on replacing !subst with !replace in the near future.

[Paul-C-Anagnostopoulos]

Clean up the relevant clang tidies.

[jansvoboda11]

Thanks for working on this! This will LGTM with the nits fixed.

llvm/docs/TableGen/ProgRef.rst

1728

This should be indented with 4 spaces as the rest of the operators.

llvm/include/llvm/TableGen/Record.h

832

Move unrelated/stylistic changes to a separate patch.

llvm/lib/TableGen/Record.cpp

1388

Move unrelated/stylistic changes to a separate patch.

llvm/lib/TableGen/TGParser.cpp

1505

Move unrelated/stylistic changes to a separate patch.

1753

Move unrelated/stylistic changes to a separate patch.

[Paul-C-Anagnostopoulos]

I'm afraid I may have gotten your hopes up. It turns out that it's quite difficult to add an assert statement given the structure of the TableGen parser. A couple of the issues:

1. It's not clear at all when the assert expression should be evaluated, particularly when it appears in a def or class.

2. There is no straightforward mechanism for carrying an assertion along with a multiclass definition, for use when the multiclass is instantiated.

I haven't given up, but it will take some time.

[Paul-C-Anagnostopoulos]

llvm/include/llvm/TableGen/Record.h

832

I wouldn't say this is unrelated, since it is the enum that contains SUBSTR. The previous sort order was apparently arbitrary.

llvm/lib/TableGen/Record.cpp

1388

Likewise, the previous sort order was apparently arbitrary.

[Paul-C-Anagnostopoulos]

Incorporated @jansvoboda11 comments.

[Paul-C-Anagnostopoulos]

llvm/docs/TableGen/ProgRef.rst

1728

I will rewrap the lines before I push this revision.

[jansvoboda11]

llvm/include/llvm/TableGen/Record.h

832

I understand.

However, it's a good practice to put formatting changes (and changes that introduce no functionality change) into separate "NFC" commits.
This helps to keep the interesting patches short and easy to understand.

In this case, you can create new NFC patch that reorders the enum cases and rebase this patch on top of the new one.

[jansvoboda11]

Yeah, there's no easy way to implement it right now.

I think looking into how loops and if statements are handle might be useful. Their ASTs are stored in the Loops member and are interpreted later on during multiclass instantiation.

Generalizing that infrastructure might be a good start. If we could store different kinds of ASTs there and handle them in specific ways during the instantiation, we might be able to inject the assertion handling there.

In D93419#2463283, @Paul-C-Anagnostopoulos wrote:

I'm afraid I may have gotten your hopes up. It turns out that it's quite difficult to add an assert statement given the structure of the TableGen parser. A couple of the issues:

1. It's not clear at all when the assert expression should be evaluated, particularly when it appears in a def or class.

2. There is no straightforward mechanism for carrying an assertion along with a multiclass definition, for use when the multiclass is instantiated.

I haven't given up, but it will take some time.

[Paul-C-Anagnostopoulos]

llvm/include/llvm/TableGen/Record.h

832

But then if I revert to the previous order, where should I insert SUBSTR? New ones have not necessarily been inserted at the end of the list. Anyway, I'll revert to the original order.

[Paul-C-Anagnostopoulos]

Yes, that is what needs to be done: The assertions have to be stored somehow and checked later.

The same goes for assertions in classes and records. Just as with field values, they have to be evaluated after the record is built. But that may feel wrong when writing something like this:

int foo = 13;
assert ...foo...
let foo = 42;

[thakis]

Seems to break tests: http://45.33.8.238/linux/35793/step_12.txt

[Paul-C-Anagnostopoulos]

Works like a charm when I run the TableGen tests on my machine. Hmm.

[Paul-C-Anagnostopoulos]

I reverted this revision.

Now I expect the directive2.td test to fail, because it does on my machine.

[RKSimon]

llvm/lib/TableGen/TGParser.cpp

1698

@Paul-C-Anagnostopoulos This might be the cause of the build failures - SIZE_MAX (unsigned ~0ULL) being seen as a -ve value when cast to int64_t

[Paul-C-Anagnostopoulos]

I'm sorry, what is a -ve value?

What is the correct way to specify the maximum size value?

[RKSimon]

In D93419#2466025, @Paul-C-Anagnostopoulos wrote:

I'm sorry, what is a -ve value?

Sorry - "-ve" is just shorthand for "negative".

What is the correct way to specify the maximum size value?

RHS = IntInit::get(std::numeric_limits<int64_t>::max())

is probably better - but I haven't tested it

[Paul-C-Anagnostopoulos]

Well now, that's new to me. Thanks!

The value of std::numeric_limits<int64_t>::max() is 0x7FFFFFFFFFFFFFFF.

What I wrote before seems like the perfect opportunity for a compiler warning.

[Paul-C-Anagnostopoulos]

What is the correct way to copy the first !substr commit and then amend it with the fix for this build problem?

Never mind, I falsely assumed that -amend does not make a new commit, but of course it does.

[Paul-C-Anagnostopoulos]

Change SIZE_MAX to std::numeric_limits<int64_t>::max() to fix a build failure.

[RKSimon]

Do you have a linux (or wsl?) machine that you can test this?

[Paul-C-Anagnostopoulos]

I'm afraid not. However, a search of the code base reveals that std::numeric_limits<int64_t>::max() is used all over the place, so I think we're okay.

[RKSimon]

LGTM (with one minor style fix) - but please watch the buildbots after the commit

llvm/lib/TableGen/TGParser.cpp

1501

(style) remove unnecessary braces

llvm/docs/TableGen/ProgRef.rst

 .. productionlist::
    BangOperator: one of
                : !add        !and         !cast        !con         !dag 
                : !empty      !eq          !foldl       !foreach     !filter
                : !ge         !getdagop    !gt          !head        !if
                : !interleave !isa         !le          !listconcat  !listsplat
                : !lt         !mul         !ne          !not         !or
                : !setdagop   !shl         !size        !sra         !srl
-               : !strconcat  !sub         !subst       !tail        !xor
+               : !strconcat  !sub         !subst       !substr      !tail
+               : !xor
 
 The ``!cond`` operator has a slightly different
 syntax compared to other bang operators, so it is defined separately:
 
 .. productionlist::
    CondOperator: !cond
 
 See `Appendix A: Bang Operators`_ for a description of each bang operator.
``!subst(``\ *target*\ ``,`` *repl*\ ``,`` *value*\ ``)``
     This operator replaces all occurrences of the *target* in the *value* with
     the *repl* and produces the resulting value. The *value* can
     be a string, in which case substring substitution is performed.
 
     The *value* can be a record name, in which case the operator produces the *repl*
     record if the *target* record name equals the *value* record name; otherwise it
     produces the *value*.
 
+``!substr(``\ *string*\ ``,`` *start*\ [``,`` *length*]\ ``)``
+    This operator extracts a substring of the given *string*. The starting position
+    of the substring is specified by *start*, which can range between 0 and the 
+    length of the string. The length of the substring is specified by *length*;
+    if not specified, the rest of the string is extracted. The *start* and *length*
+    arguments must be integers.
+
 ``!tail(``\ *a*\ ``)``
     This operator produces a new list with all the elements
     of the list *a* except for the zeroth one. (See also ``!head``.)
 
 ``!xor(``\ *a*\ ``,`` *b*\ ``, ...)``
     This operator does a bitwise EXCLUSIVE OR on *a*, *b*, etc., and produces
     the result. A logical XOR can be performed if all the arguments are either
     0 or 1.

llvm/include/llvm/TableGen/Record.h

public:
   Init *resolveReferences(Resolver &R) const override;
 
   std::string getAsString() const override;
 };
 
 /// !op (X, Y, Z) - Combine two inits.
 class TernOpInit : public OpInit, public FoldingSetNode {
 public:
-  enum TernaryOp : uint8_t { SUBST, FOREACH, FILTER, IF, DAG };
+  enum TernaryOp : uint8_t { DAG, FILTER, FOREACH, IF, SUBST, SUBSTR };
 
 private:
   Init *LHS, *MHS, *RHS;
 
   TernOpInit(TernaryOp opc, Init *lhs, Init *mhs, Init *rhs,
              RecTy *Type) :
       OpInit(IK_TernOpInit, Type, opc), LHS(lhs), MHS(mhs), RHS(rhs) {}
 

llvm/lib/TableGen/Record.cpp

if (MHSok && RHSok && (!MHSl || !RHSl || MHSl->size() == RHSl->size())) {
         if (!isa<StringInit>(Name) && !isa<UnsetInit>(Name))
           return const_cast<TernOpInit *>(this);
         Children.emplace_back(Node, dyn_cast<StringInit>(Name));
       }
       return DagInit::get(LHS, nullptr, Children);
     }
     break;
   }
+
+  case SUBSTR: {
+    StringInit *LHSs = dyn_cast<StringInit>(LHS);
+    IntInit *MHSi = dyn_cast<IntInit>(MHS);
+    IntInit *RHSi = dyn_cast<IntInit>(RHS);
+    if (LHSs && MHSi && RHSi) {
+      int64_t StringSize = LHSs->getValue().size();
+      int64_t Start = MHSi->getValue();
+      int64_t Length = RHSi->getValue();
+      if (Start < 0 || Start > StringSize)
+        PrintError(CurRec->getLoc(),
+                   Twine("!substr start position is out of range 0...") +
+                       std::to_string(StringSize) + ": " +
+                       std::to_string(Start));
+      if (Length < 0)
+        PrintError(CurRec->getLoc(), "!substr length must be nonnegative");
+      return StringInit::get(LHSs->getValue().substr(Start, Length),
+                             LHSs->getFormat());
+    }
+    break;
+  }
   }
 
   return const_cast<TernOpInit *>(this);
 }
 
 Init *TernOpInit::resolveReferences(Resolver &R) const {
   Init *lhs = LHS->resolveReferences(R);
 
return (TernOpInit::get(getOpcode(), lhs, mhs, rhs, getType()))
         ->Fold(R.getCurrentRecord());
   return const_cast<TernOpInit *>(this);
 }
 
 std::string TernOpInit::getAsString() const {
   std::string Result;
   bool UnquotedLHS = false;
   switch (getOpcode()) {
-  case SUBST: Result = "!subst"; break;
-  case FOREACH: Result = "!foreach"; UnquotedLHS = true; break;
+  case DAG: Result = "!dag"; break;
   case FILTER: Result = "!filter"; UnquotedLHS = true; break;
+  case FOREACH: Result = "!foreach"; UnquotedLHS = true; break;
   case IF: Result = "!if"; break;
-  case DAG: Result = "!dag"; break;
+  case SUBST: Result = "!subst"; break;
+  case SUBSTR: Result = "!substr"; break;
   }
   return (Result + "(" +
           (UnquotedLHS ? LHS->getAsUnquotedString() : LHS->getAsString()) +
           ", " + MHS->getAsString() + ", " + RHS->getAsString() + ")");
 }
 
 static void ProfileFoldOpInit(FoldingSetNodeID &ID, Init *A, Init *B,
                               Init *Start, Init *List, Init *Expr,

llvm/lib/TableGen/TGLexer.h

enum TokKind {
     // Reserved keywords. ('ElseKW' is named to distinguish it from the
     // existing 'Else' that means the preprocessor #else.)
     Bit, Bits, Class, Code, Dag, Def, Defm, Defset, Defvar, ElseKW, FalseKW,
     Field, Foreach, If, In, Include, Int, Let, List, MultiClass,
     String, Then, TrueKW,
 
     // Bang operators.
     XConcat, XADD, XSUB, XMUL, XNOT, XAND, XOR, XXOR, XSRA, XSRL, XSHL,
-    XListConcat, XListSplat, XStrConcat, XInterleave, XCast, XSubst, XForEach,
-    XFilter, XFoldl, XHead, XTail, XSize, XEmpty, XIf, XCond, XEq, XIsA,
-    XDag, XNe, XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
+    XListConcat, XListSplat, XStrConcat, XInterleave, XSubstr, XCast,
+    XSubst, XForEach, XFilter, XFoldl, XHead, XTail, XSize, XEmpty, XIf,
+    XCond, XEq, XIsA, XDag, XNe, XLe, XLt, XGe, XGt, XSetDagOp, XGetDagOp,
 
     // Boolean literals.
     TrueVal, FalseVal,
 
     // Integer value.
     IntVal,
 
     // Binary constant.  Note that these are sized according to the number of

llvm/lib/TableGen/TGLexer.cpp

tgtok::TokKind Kind =
     .Case("subst", tgtok::XSubst)
     .Case("foldl", tgtok::XFoldl)
     .Case("foreach", tgtok::XForEach)
     .Case("filter", tgtok::XFilter)
     .Case("listconcat", tgtok::XListConcat)
     .Case("listsplat", tgtok::XListSplat)
     .Case("strconcat", tgtok::XStrConcat)
     .Case("interleave", tgtok::XInterleave)
+    .Case("substr", tgtok::XSubstr)
     .Cases("setdagop", "setop", tgtok::XSetDagOp) // !setop is deprecated.
     .Cases("getdagop", "getop", tgtok::XGetDagOp) // !getop is deprecated.
     .Default(tgtok::Error);
 
   return Kind != tgtok::Error ? Kind : ReturnError(Start-1, "Unknown operator");
 }
 
 bool TGLexer::prepExitInclude(bool IncludeStackMustBeEmpty) {

llvm/lib/TableGen/TGParser.h

void ParseDagArgList(
       Record *CurRec);
   bool ParseOptionalRangeList(SmallVectorImpl<unsigned> &Ranges);
   bool ParseOptionalBitList(SmallVectorImpl<unsigned> &Ranges);
   void ParseRangeList(SmallVectorImpl<unsigned> &Result);
   bool ParseRangePiece(SmallVectorImpl<unsigned> &Ranges,
                        TypedInit *FirstItem = nullptr);
   RecTy *ParseType();
   Init *ParseOperation(Record *CurRec, RecTy *ItemType);
+  Init *ParseOperationSubstr(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType);
   Init *ParseOperationCond(Record *CurRec, RecTy *ItemType);
   RecTy *ParseOperatorType();
   Init *ParseObjectName(MultiClass *CurMultiClass);
   Record *ParseClassID();
   MultiClass *ParseMultiClassID();
   bool ApplyLetStack(Record *CurRec);
   bool ApplyLetStack(RecordsEntry &Entry);
 };
 
 } // end namespace llvm
 
 #endif

llvm/lib/TableGen/TGParser.cpp

case tgtok::XSubst: {
       }
       Type = RHSt->getType();
       break;
     }
     }
     return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
   }
 
+  case tgtok::XSubstr: {
+    return ParseOperationSubstr(CurRec, ItemType);
+  }
+
   case tgtok::XCond:
     return ParseOperationCond(CurRec, ItemType);
 
   case tgtok::XFoldl: {
     // Value ::= !foldl '(' Value ',' Value ',' Id ',' Id ',' Expr ')'
     Lex.Lex(); // eat the operation
     if (!consume(tgtok::l_paren)) {
       TokError("expected '(' after !foldl");
       return nullptr;
     }
 
RecTy *TGParser::ParseOperatorType() {
   if (!consume(tgtok::greater)) {
     TokError("expected type name for operator");
     return nullptr;
   }
 
   return Type;
 }
 
+/// Parse the !substr operation. Return null on error.
+///
+/// Substr ::= !substr(string, start-int [, length-int]) => string
+Init *TGParser::ParseOperationSubstr(Record *CurRec, RecTy *ItemType) {
+  TernOpInit::TernaryOp Code = TernOpInit::SUBSTR;
+  RecTy *Type = StringRecTy::get();
+
+  Lex.Lex(); // eat the operation
+
+  if (!consume(tgtok::l_paren)) {
+    TokError("expected '(' after !substr operator");
+    return nullptr;
+  }
+
+  Init *LHS = ParseValue(CurRec);
+  if (!LHS)
+    return nullptr;
+
+  if (!consume(tgtok::comma)) {
+    TokError("expected ',' in !substr operator");
+    return nullptr;
+  }
+
+  SMLoc MHSLoc = Lex.getLoc();
+  Init *MHS = ParseValue(CurRec);
+  if (!MHS)
+    return nullptr;
+
+  SMLoc RHSLoc = Lex.getLoc();
+  Init *RHS;
+  if (consume(tgtok::comma)) {
+    RHSLoc = Lex.getLoc();
+    RHS = ParseValue(CurRec);
+    if (!RHS)
+      return nullptr;
+  } else {
+    RHS = IntInit::get(SIZE_MAX);
+  }
+
+  if (!consume(tgtok::r_paren)) {
+    TokError("expected ')' in !substr operator");
+    return nullptr;
+  }
+
+  if (ItemType && !Type->typeIsConvertibleTo(ItemType)) {
+    Error(RHSLoc, Twine("expected value of type '") +
+                  ItemType->getAsString() + "', got '" +
+                  Type->getAsString() + "'");
+  }
+
+  TypedInit *LHSt = dyn_cast<TypedInit>(LHS);
+  if (!LHSt && !isa<UnsetInit>(LHS)) {
+    TokError("could not determine type of the string in !substr");
+    return nullptr;
+  }
+  if (LHSt && !isa<StringRecTy>(LHSt->getType())) {
+    TokError(Twine("expected string, got type '") +
+             LHSt->getType()->getAsString() + "'");
+    return nullptr;
+  }
+
+  TypedInit *MHSt = dyn_cast<TypedInit>(MHS);
+  if (!MHSt && !isa<UnsetInit>(MHS)) {
+    TokError("could not determine type of the start position in !substr");
+    return nullptr;
+  }
+  if (MHSt && !isa<IntRecTy>(MHSt->getType())) {
+    Error(MHSLoc, Twine("expected int, got type '") +
+                      MHSt->getType()->getAsString() + "'");
+    return nullptr;
+  }
+
+  if (RHS) {
+    TypedInit *RHSt = dyn_cast<TypedInit>(RHS);
+    if (!RHSt && !isa<UnsetInit>(RHS)) {
+      TokError("could not determine type of the length in !substr");
+      return nullptr;
+    }
+    if (RHSt && !isa<IntRecTy>(RHSt->getType())) {
+      TokError(Twine("expected int, got type '") +
+               RHSt->getType()->getAsString() + "'");
+      return nullptr;
+    }
+  }
+
+  return (TernOpInit::get(Code, LHS, MHS, RHS, Type))->Fold(CurRec);
+}
+
 /// Parse the !foreach and !filter operations. Return null on error.
 ///
 /// ForEach ::= !foreach(ID, list-or-dag, expr) => list<expr type>
 /// Filter  ::= !foreach(ID, list, predicate) ==> list<list type>
 Init *TGParser::ParseOperationForEachFilter(Record *CurRec, RecTy *ItemType) { 
   SMLoc OpLoc = Lex.getLoc();
   tgtok::TokKind Operation = Lex.getCode();
   Lex.Lex(); // eat the operation
   if (Lex.getCode() != tgtok::l_paren) {
     TokError("expected '(' after !foreach/!filter");
     return nullptr;
   }
Init *TGParser::ParseSimpleValue(Record *CurRec, RecTy *ItemType,
   case tgtok::XStrConcat:
   case tgtok::XInterleave:
   case tgtok::XSetDagOp: // Value ::= !binop '(' Value ',' Value ')'
   case tgtok::XIf:
   case tgtok::XCond:
   case tgtok::XFoldl:
   case tgtok::XForEach:
   case tgtok::XFilter:
-  case tgtok::XSubst: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
+  case tgtok::XSubst:
+  case tgtok::XSubstr: { // Value ::= !ternop '(' Value ',' Value ',' Value ')'
     return ParseOperation(CurRec, ItemType);
   }
   }
 
   return R;
 }
 
 /// ParseValue - Parse a tblgen value.  This returns null on error.

llvm/test/TableGen/substr.td

+// RUN: llvm-tblgen %s | FileCheck %s
+// RUN: not llvm-tblgen -DERROR1 %s 2>&1 | FileCheck --check-prefix=ERROR1 %s
+
+defvar claim = "This is the end of the world!";
+
+// CHECK: def Rec1
+// CHECK:   fullNoLength = "This is the end of the world!";
+// CHECK:   fullLength = "This is the end of the world!";
+// CHECK:   thisIsTheEnd = "This is the end";
+// CHECK:   DoorsSong = "the end";
+// CHECK:   finalNoLength = "end of the world!";
+// CHECK:   finalLength = "end of the world!";
+
+def Rec1 {
+  string fullNoLength = !substr(claim, 0);
+  string fullLength = !substr(claim, 0, 999);
+  string thisIsTheEnd = !substr(claim, 0, 15);
+  string DoorsSong = !substr(claim, 8, 7);
+  string finalNoLength = !substr(claim, 12);
+  string finalLength = !substr(claim, 12, !sub(!size(claim), 12));
+}
+
+// CHECK: def Rec2 {
+// CHECK:   lastName = "Flintstone";
+
+def Rec2 {
+  string firstName = "Fred";
+  string name = firstName # " " # "Flintstone";
+  string lastName = !substr(name, !add(!size(firstName), 1));
+}
+
+// CHECK: def Rec3 {
+// CHECK:   test1 = "";
+// CHECK:   test2 = "";
+// CHECK:   test3 = "";
+// CHECK:   test4 = "h";
+// CHECK:   test5 = "hello";
+// CHECK:   test6 = "";
+
+def Rec3 {
+  string test1 = !substr("", 0, 0);
+  string test2 = !substr("", 0, 9);
+  string test3 = !substr("hello", 0, 0);
+  string test4 = !substr("hello", 0, 1);
+  string test5 = !substr("hello", 0, 99);
+  string test6 = !substr("hello", 5, 99);
+}
+
+// CHECK: def Rec4
+// CHECK:   message = "This is the end of the world!";
+// CHECK:   messagePrefix = "This is th...";
+// CHECK:   warning = "Bad message: 'This is th...'";
+
+class C<string msg> {
+  string message = msg;
+  string messagePrefix = !substr(message, 0, 10) # "...";
+}
+
+def Rec4 : C<claim> {
+  string warning = "Bad message: '" # messagePrefix # "'";
+}
+
+#ifdef ERROR1
+
+// ERROR1: expected string, got type 'int'
+// ERROR1: expected int, got type 'bits<3>'
+// ERROR1: expected int, got type 'string'
+// ERROR1: !substr start position is out of range 0...29: 30
+// ERROR1: !substr length must be nonnegative
+
+def Rec8 {
+  string claim1 = !substr(42, 0, 3);
+  string claim2 = !substr(claim, 0b101);
+  string claim3 = !substr(claim, 0, "oops");
+}
+
+def Rec9 {
+  string claim1 = !substr(claim, !add(!size(claim), 1));
+  string claim2 = !substr(claim, 0, -13);
+}
+#endif