How do we want error handling to finally look like?

[rsmmr]

We have a PR open that will add manual backtracking through &try/backtrack(). That's a straight port of a feature from the old Spicy research prototype, but it's certainly not the last word on error handling. Curious to hear thoughts on use cases we should support, and proposals for syntax to do so.

(Note that there's also a separate topic of automatic error recovery. I'm planing to eventually port the approach of the research prototype over for that as well, which performs automatic re-synchronization at some later point in the input stream where we can continue parsing after an earlier error; this is tracked by #23).

[duffy-ocraven]

I've so-far identified three distinct major paradigms of error handling when writing a parser.

1. when &try is used for a field which is an optional field, with paradigm: if what you see during parsing at the needful moment isn't the signature of the optional field, then treat the input-stream as omitting that optional field, and go on. That is what the existing backtrack-on-error.spicy code exactly manifests, though it leaves vestiges of a partially constructed instance of that optional field. I expect that for a better design of error handling when &try is used for a field which is an optional field, that a partially constructed instance should be automatically unset, rather than making the parser author explicitly make unset calls. I suggest &try &optional as the syntax to denote these times. That can guide when a partially constructed instance should be automatically unset.

2. Another major paradigm to support in how error handling looks is detection of substandard encodings in the input-stream. Not like an optional field, so not something that can be omitted. But perhaps non-compliant with the latest version of the protocol, with regard to something, especially potentially a trailing something, such that by looking for it, the parse inadvertently moves past the end of the encoding in the input-stream and gobbles some part of the next item. A real-world example comes from timeAndTimezone in SS7. It is a length seven or eight series of octets. Eight if the century was specified, seven if not. About 21 years ago, the whole world became Y2K aware, so almost all implementations now would be eight. Gobbling the eight bytes and passing those to a subroutine will make logical sense. But if the number in the initial byte is anything other than 19 or 20, so almost certainly a year-within-century rather than the value of 19 or 20 which is characteristic of a currently plausible century, error handling can invoke backtrack().

3. The most important paradigm we will want to support in how error handling looks, is to be able to resynchronize after a library routine raises an exception. Much of the content that spicy will be applied to will have accurate leading length indicators in headers in the protocol, but will have subtle errors either in the encoding or in the generality and provision for allowed alternatives, in the content parsing of the protocol. In those cases, we can and must "dust ourselves off and carry on". It might be using the &try, and certainly until there is any other provision, the current support will encourage parser authors of necessity to use &try. Keeping track of the accurate "how much to munch to get aligned with the next thing" is easily programmed. When anything throws an exception, with &try there is then the opportunity to accurately position at start of an encoding. There an explicit conditional noticing that the backtrack had been invoked (such as by setting a flag in %on error), can use an else path to jump over whatever the problem was, to the next encoded unit, simply using the accurate length indicator from the header of the problematic one.

These three are not a map to the whole "how we want error handling to finally look", and by illustration with BTest examples of what seems intuitively correct we will further this discussion. But &try is a HUGE advance and very welcome. That alone was enough to make it timely now to at least make sure we have the syntactic support that we desire, for the above three paradigms.

[rsmmr]

There's also a related question if we want lower-level exception primitives (throw/catch-style), even independent of parsing errors.

[duffy-ocraven]

What is the intended supported syntax with &try foreach following a member field which is a vector? That those words can appear in either order? That the logical fallback position for that single &try is repositioned with each iteration?

[rsmmr]

Yes, order of attributes doesn't matter.

The fallback position will be the following field (i.e., subsequent to the container). It might in principle work to associate the &try with the container element (using the (...) syntax) but (1) I haven't tried that, and (2) segmentally that doesn't seem useful as it would just walk down the same parse path again, eventually hitting the same backtrack.

[duffy-ocraven]

If you are envisioning that it would just walk down the same parse path again, then you are seeing container &try limited in a manner where it does not serve above scenario #3. I was very much hoping that container &try would be the most common way to express scenario #3, since elements of the container if a header-length specifies the extent of them, are a natural place to advance, to go past whatever triggered the backtrack. I should illustrate this with an example, and I will later. But I wanted to start here more quickly with the subdiscussion of whether you can see container &try potentially serving for scenario #3?

[duffy-ocraven]

Something like this syntax:

module Issue_629_preferred_container_syntax;
global skipOver = False;
    
public type CollectionOfBlocks = unit {
  blks: BlockWithReliableHeader[] foreach &try;
};

# uses %on error activated "skipOver" to utilize backtrack as error-recovery
type BlockWithReliableHeader = unit {
    var justHeaderOrAllIfSkip: uint64;
    var theStaticSizeOfRemainingHdr: uint64;
    on %init {
      self.theStaticSizeOfRemainingHdr = 2;
      self.justHeaderOrAllIfSkip = self.theStaticSizeOfRemainingHdr;
    }
  blkLen: uint16 { if (skipOver) { self.justHeaderOrAllIfSkip = self.blkLen - 2; skipOver = False; } } # re-priming it for the next time
   : bytes &size = self.justHeaderOrAllIfSkip;
  blkContent: bytes &size = self.blkLen - self.justHeaderOrAllIfSkip - 2;
    on blkContent {
      if (*self.blkContent.at(0) != 0x20) self.backtrack;
    }
    on %error {
      skipOver = True;
    }
    on %done {
      print (self);
    }
};

[rsmmr]

The current &try/backtrack isn't quite the right mechanism for (3) IMO, or at least I think it should not be out primary mechanism there because I think we can do better (in the sense of: more automated, more powerful). I was trying to keep the discussion of recovery separate, but I'm realizing it's all pretty closely related, so that probably isn't very helpful.

So, we definitely want to support what your example shows: if one element of an array fails to parse, skip ahead to the next one and continue. The old prototype supported that differently, the best summary is in the Spicy paper, see Section 2.6 here: http://www.icir.org/robin/papers/acsac16-spicy.pdf. The old tests show more on how to use this: https://github.com/rsmmr/hilti/tree/master/tests/spicy/synchronize. The &synchronized works very similar to the &try in your example (and maybe we could indeed use the same attribute in both cases), and then the sub-units express how they can be re-aligned with the data. I don't recall if the "skip a certain amount of bytes" was already supported, but I'm sure we can fit that in there as well. I'd be curious to hear your thoughts on this scheme, so far I have been planning to port this over.

[rsmmr]

Scenario (3) is "totally confident that the extent of the item I am working upon is known, but the generality and capability of the spicy parser implementation vs the content encountered have an insurmountable mismatch". I guess my coming from mostly binary-encoded protocols has me focused on that, vs text protocols where regexp has applicability.

I believe we are on the same page here. With (3) we can definitely fully recover, no guessing needed. In the regex case, it's a heuristic than may or not may work. To me, both are still similar/releated in that we (a) first have an error, and (b) then switch into some form recovery mode to find a new position to continue, and (c) use one out of a set of mechanisms to do that (in (3) we just know a fixed length to skip; with regex, we'll start looking).

if we utilize &parse-from liberally and make it do the right thing.

Here I don't quite follow, or better: it's not &parse-from that's the key here IMO. &parse-from requires copying/creating new data that's then parsed independently of, and detached from, the current input stream. That doesn't feel like the right tool here (unless I'm missing something?). But I'm with you that we can make Spicy figure this out. One immediate case would if all fields inside that content are actually already fixed size by their definition: Spicy could just add them up and would know how many bytes to expect and potentially skip. That's probably not the case very often, but we can also add a way to explicitly specify the size of an outer layer just for the purpose of skipping, maybe be even reusing the &size attribute at higher layers for that (so you could say x: Item &size=32 and it would skip those 32 bytes if there's an error anywhere inside the Item.).

I'm also wondering if this "bail out and recover" should trigger automatically on any error, or if want to limit it to certain places. The old &synchronize is for the latter: explicitly mark where recovery may happen. I'm leaning towards continuing to require that, to make it explicit, but open to thoughts.

[duffy-ocraven]

The old &synchronize, or now (perhaps as a interim) the &try to explicitly mark where recovery may happen, is one characteristic in how we want error handling to finally look, that I definitely think we should hold onto. Cognitively for the parser author, that is a noteworthy "place" in the code, to use spatial layout of the code to accurately reason about what comes after a backtrack/recover.

[duffy-ocraven]

Where you remarked: "if all fields inside that content are actually already fixed size by their definition, Spicy could just add them up and would know how many bytes to expect and potentially skip." My experience aligns with yours, that that's not the case very often because padding rules vary all over. But setting aside that "adding them up", it would in contrast be quite commonly utilized if there was a way to explicitly specify the size of an outer layer just for the purpose of skipping. A header field in MANY protocols explicitly specifies the size of an outer layer.

[duffy-ocraven]

I agree with you about leaving &parse-from as-is, for situations requiring copying that's then parsed independently of, and detached from, the current input stream. Your syntax of Item &size= if that explicitly specifies the size of an outer layer, gives the two capabilities that I see as most useful. That it can: "bail out and recover" on any error at the most recent pending &synchronize. And that: marks both ends, to automatically guard violations which create pointer-addition or end-of-field positions for purported sub-items, that are past either the beginning or end. I mention the beginning which might seem far-fetched, but inadvertent sign-extension of a value that is then added to a position, exceeds the beginning boundary but does not get caught by a "check to ensure less-than the end" comparison.

[duffy-ocraven]

Note for your examplex: Item &size=32, that also common (perhaps even more common) is a x: Items[] foreach &try &size=$$.hdr.entireLen I'm not sure presently that expression is capable of being dynamically assigned with that syntax, but we can find the syntax that works, if we agree that the concept is worthy.

[bbannier]

Sorry for joining this discussion so late. Since my response became pretty long here's a TLDR;:

• settle on stringly typed errors in script-land for now
• introduce a primitive for scripts to raise errors
• introduce a primitive to access the current error in %error hooks
• allow %init/%done/%error hooks in more places, and
• look for ways to replace existing features with something more uniform 😆

---

I wonder if we keep the premise that backtracking is orthogonal to error handling, we might be able to make the later more powerful by extending the current hooks and allowing parsers to raise errors.

E.g., given a unit

type X = unit {
  a: uint8;
  b: uint8[] &size=2;
  c: F[10]; // Unit (or with #604 field) type `F`.

  on %done {};
  on %error {}
};

at least the following seem hard:

1. It is very hard to trigger a parse error anywhere. This makes it e.g., hard to trigger a parse error from the %done hook if some unit-level invariants are violated (e.g., a = sum(b)).

2. There is no good go way to perform field-level semantic validation. While one could add a %done-style hook to the field one again cannot raise an error, e.g.,

   // IMAGINARY CONSTRUCT `raise`.
   a: uint8 { if ($$ % 2) raise("'a' must be even"); }
   

3. If a field fails to parse one can only catch the error in the unit-level %error hook where context on where the failure originated is lost. Imagine that e.g., one of the values X.c fails to parse; we wont know that the c field failed to parse, and even less which of them.

Triggering errors

For issue (1) we would need a construct to raise errors from scripts. Currently, the runtime can trigger parse errors and logic errors, and I do not think distinguishing them from an error recovery perspective is too useful (e.g., writing error recovery for integer overflows in addition to parse errors seems like a reasonable ask). Depending on which additional tools we'd provide to inspect error state from error handlers we might not need that distinction on the script-land triggering side either, and just raising a single error type might be good enough. So let's say we'd introduce a raise statement/function which triggers an error which is just a string.

Handling errors

The current error handling seems to be not granular enough. We allow %error hooks at unit scope where they have access to the full unit via $$ for inspection, though, so one can currently work around that limitation.

Interestingly Spicy already provides other hook-like constructs, e.g., while-else,

local i: uint8 = 0;
while (True) {
  ++i;
  break;
} else {
  print(i);
}

or unit switch-if,

type X = unit {
  a: uint8;

  switch (self.a) {
      0 -> b1: uint8[1],
      1 -> b1: uint8[2],
  } if (self.a < 2);
};

While-else acts like a special case of a %done hook for blocks, while at least if looking at it from an error recovery angle unit switch-if could act in above example as a workaround for missing tooling in field-level validation

It seems these examples would also work if we were to allow hooks on other constructs, e.g., unit fields, blocks, and functions, e.g., above examples:

// While-else.

local i: uint8 = 0;
while (True) {
  ++i;
  break;
} on %done {
  print(i);
}

// or even:
while (True) {
  ++i;
  break;
} on %init {
  local i: uint8 = 0;
} on %done {
  print(i);
}

// Unit-switch. Two approaches with different semantics.

// Enforce a global invariant on `X.a`.
type X = unit {
  a: uint8 on %done { if ($$ >= 2) raise("impossible value %d for 'a'" % $$); }

  // Even today with less explicit syntax:
  //
  //    a: uint8 { if ($$ >= 2) ... };

  switch (self.a) {
      0 -> b1: uint8[1],
      1 -> b1: uint8[2],
  }
};

// Conditionally enable unit switch block.
type X = unit {
  a: uint8;

  switch (self.parse_b) {
      0 -> b1: uint8[1],
      1 -> b1: uint8[2],
  } on %init {
    if (self.a >= 2)
      continue; // IMAGINARY: Skip preceeding block.
  }
};

// Even C++-style function-try-block.
function foo(x: uint8) : uint8 {
  return x*x;
} on %error {
  print("failure to foo x: %s" % $error); // See below for `$error`.
  return 0; // Required return value for finalizing hooks like `%done` and `%error`.
            // Alternatively: raising error requires no return.

While we would only need field-level %error hooks to get finer error handling, it seems interesting to support at least %done and %init as well (if only for symmetry).

Accessing error state

With these imaginary extensions we could rewrite the original example,

type F;

type X = unit {
  a: uint8 on %done {
    if ($$ % 2) raise("'a' must be even"); 
  }

  b: uint8[] &size=2;
  c: F[10] on %error {
      // IMAGINARY SYNTAX `$error`.
      print("recovering after failure to parse entry %d of 'c': %s" % (|$$|, $error));

      // Prevent propagation of error.
  };

  on %done {
    local sum: uint64 = 0;
    for (b in self.b) { sum += b; }
    if (self.a != sum) { raise("sum invariant violated: %d vs %d" % (b, sum)); }
  };

  on %error {
    // Not stricyly needed anymore, but usable to e.g., decorate upstream errors.
    // IMAGINARY SYNTAX `$error`.
    raise("failure to parse 'X': %s" % $error);
  }
};

We seem to be able to validate preconditions and handle errors locally, and trigger errors from scripts. What is still missing is a way to access the current error in an error handler for which I wrote a magic imaginary accessors $error in above example. In a world where errors are just strings this would give access to a string. String errors seem to compose nicely (raise("on level X: %s % $error)).

Relation to synchronization

Issue #23 is about adding synchronization from the original prototype. There this was achieved by adding unit-scope attributes to indicate what content to skip, e.g., from the original paper

type RequestLine = unit {
  %synchronize-at = /(GET|POST|HEAD) /;
  method  : Token;
          : WhiteSpace;
  uri     : Token;
          : WhiteSpace;
          : /HTTP\//;
  version : /[0-9]+\.[0-9]*/;
          : Newline;
};

This works, but I wonder whether instead allowing these constructs on the the block scope in addition to unit scope would make the feature more powerful, e.g.,

type RequestLine = unit {
  method  : Token;
          : WhiteSpace;
  uri     : Token;
          : WhiteSpace;
          : /HTTP\//;
  version : /[0-9]+\.[0-9]*/;
          : Newline;

  on %error {
    // Skip parsing of `$$` until matcher.
    %synchronize-at = /(GET|POST|HEAD) /;

    // Or more explicitly:
    $$.%synchronize-at(/(GET|POST|HEAD) /);
  }
};

I could imagine that block-scope synchronization primitives would also be useful in e.g., the imaginary field hooks I mentioned above. It seems e.g., possible to implement some of the features of backtracing #606 with that.