Handling indentation

[flying-sheep]

Hi! I don’t know if this is a question or a feature request, but I want to parse reStructuredText. It allows nesting blocks, and indentation works in a special way:

Several constructs begin with a marker, and the body of the construct must be indented relative to the marker. For constructs using simple markers (bullet lists, enumerated lists, footnotes, citations, hyperlink targets, directives, and comments), the level of indentation of the body is determined by the position of the first line of text, which begins on the same line as the marker. For example, bullet list bodies must be indented by at least two columns relative to the left edge of the bullet:

- This is the first line of a bullet list
  item's paragraph.  All lines must align
  relative to the first line.  [1]_

      This indented paragraph is interpreted
      as a block quote.

Because it is not sufficiently indented,
this paragraph does not belong to the list
item.

.. [1] Here's a footnote.  The second line is aligned
   with the beginning of the footnote label.  The ".."
   marker is what determines the indentation.

For constructs using complex markers (field lists and option lists), where the marker may contain arbitrary text, the indentation of the first line after the marker determines the left edge of the body. For example, field lists may have very long markers (containing the field names):

:Hello: This field has a short field name, so aligning the field
        body with the first line is feasible.

:Number-of-African-swallows-required-to-carry-a-coconut: It would
    be very difficult to align the field body with the left edge
    of the first line.  It may even be preferable not to begin the
    body on the same line as the marker.

How can I parse this? Would I parse it manually, I’d define an “indent stack” (like [2, 4] for the first example). Is the best idea to create an iterator that handles this indent stack and only feeds the blocks it found into pest? Or is there another way?

[dragostis]

#328 should be helpful here. Let me know if you need extra help and I can take a closer look!

[flying-sheep]

Not exactly, as indentation isn’t defined by just the spaces that can be pushed on the stack (as mentioned in the text). The markers also count.

Furthermore, I’d need a way to say “if the stack is empty, match "".” AFAIK, PEEK fails to match on an empty stack. I assume I’d need the following extensions

• PEEK → PEEK (as before) or PEEK(default) (matches “default” if the stack is empty)
• PUSH → PUSH(expr) (as before) or PUSH(expr, lambda) (executes the lambda on the captured range and pushes the return value)

and then I could do:

block = { PEEK("") ~ (bullet_list | …) }
bullet_list = { (bullet_list_item | empty_line)+ }
bullet_list_item = { PUSH("-" ~ " "+, m => m.replace('-', " ")) ~ line ~ block* ~ POP }
line = { !bullet_list_item ~ ANY* }

[dragostis]

Markers can probably be dealt with by having multiple choices:

block = { "-" ~ bullet_list | "^" ~ whatever }
bullet_list = { ... }
whatever = { ... }

Why do you need to know when the stack is empty?

[dragostis]

I see the issue with the pushes, though. You'd need a way to simply figure out the distance from the start of the line. I'm wondering what the smallest primitive is in order to enable this.

[flying-sheep]

You'd need a way to simply figure out the distance from the start of the line.

This is problem 1:

If I want to populate the stack with the indentation, I need to be able to push " "{x} onto the stack, while matching something{y} ~ " "{x-y} (e.g. I match "-" ~ " "{2} and push " "{3})

Of course if there would be another way than the stack, that would work too, but having a stack is the most intuitive.

Why do you need to know when the stack is empty?

This is problem 2:

Provided the stack contains the indentations of the first example, i.e. [" ", " "], I’d match the indentation via PEEK ~ line. But that should also work on an empty stack!

I could just do document = { SOI ~ PUSH("") ~ block* ~ EOI }, but then I can’t test rules right? RstParser::parse(Rule::block, ...) wouldn’t match, since parse initializes the stack empty and PEEK will not match an empty stack.

[dragostis]

I've managed to get something working. The issue here is that the order of pushing vs the order of popping is reversed, but it works if spaces only contains spaces and not tabs, for example.

[flying-sheep]

Hmm, that doesn’t work. All kinds of blocks can be nested (your rest_lines? should be something like block*)

I tried something, but I can’t get it to work: https://pest.rs/?bin=7wn0u#editor

I don’t think the PUSH/POP semantics allow for what I need.

[dragostis]

I think this is possible by using PEEK_ALL, like in the simple lists example. It uses PUSH and DROP in order to keep track of the indentation level.

[flying-sheep]

I got it. Damn, that’s hard, but you’re right, it seems possible.

https://pest.rs/?bin=jgwd2#editor

I still didn’t get nesting to work properly (see the “nested item 2”), but if you can show me that this is possible, i’m happy. (could it be that in blist_body, the POP succeeds but the PUSH doesn’t? that would explain the stack being off)

also, can you please confirm that PEEK_ALL matches "" on an empty stack?

[dragostis]

Super impressive work! 😃I really like the elegance of your example. Your example is missing a PEEK_ALL in the beginning of bullet_list. That isn't quite right. I'll have to take a better look tomorrow.

PEEK_ALL always matches when the stack is empty. Unfortunately, this needs to be better documented.

[dragostis]

I don't have a complete solution, but the issue in your example is that you need to PEEK_ALL at every line, but line accepts the new line, then calls blist_body which should first PEEK_ALL before doing anything else, but doesn't.

bullet_item =  { "-" ~ PUSH(" "+) ~ line ~ blist_body? ~ DROP }
blist_body  = _{
  // Some PEEK_ALL is needed here
  PUSH(" " ~ POP) ~ hanging_block ~ block*
}

This is quite hard since, as far as I can tell, you always need to figure out if you're a paragraph or a bullet list item. Maybe you could make use of the lookahead like this:

  &(PEEK_ALL) ~ paragraph          // paragraph at same indentation
| &(DROP ~ "-" ~ ...) ~ blist_item // bullet list item at same parent indentation

Lookaheads reset the stack to its initial position.

[flying-sheep]

I don’t think it’s possible. blist_body appears when the stack contains […, "- "], so i’d need PEEK_ALL_EXCEPT_LAST ~ PUSH(" " ~ POP).

[dragostis]

I guess the lookahead won't work because after you'd need to actually match it, correct?

If so, it might be worthwhile to be able to peek by slicing the stack with a range, I presume. Adding this would be no problem.

[flying-sheep]

exactly. I need to match it exactly because otherwise I can’t tell the parser the depth of the next indentation level:

               ← stack here: []
-  item        ← stack here: ["  "] *
   next line   ← stack here: ["   "]
   - indented  ← stack here: ["   " " "] *
     next      ← stack here: ["   " "  "]

at the * positions, the last stack entry is one space too small for the following indentation, so i need to be able to both match the correct indentation and fix the last stack entry.

[flying-sheep]

Should I create a separate issue for this?

and how would it look? I have two proposals using arrow slice syntax:

1. going from the end:

PEEK, PEEK[i], PEEK[skip..last], PEEK_ALL
skip and last are optional, default to the top (0) and bottom items the stack, so PEEK[..] is equivalent to PEEK_ALL.

I propose that it fails when you specifically request an item that doesn’t exist, but succeeds when you request an empty sequence. E.g. if there’s one item on the stack (PEEK_ALL ≡ ("stuff"))

1. PEEK[1] fails
2. PEEK[1..] fails
3. PEEK[..2] fails
4. PEEK[0] ≡ "item" succeeds
5. PEEK[..1] ≡ ("item") succeeds
6. PEEK[1..] ≡ () succeeds

This option would be intutive from the way stacks work: We usually think “i-th item from the top”

2. use negative indices

An alternative would be PEEK, PEEK[i], PEEK[start..end], PEEK_ALL

That would be more intuitive regarding item direction as the stack gets matched in bottom→top direction, written left-to-right. Then our examples would be:

1. PEEK[-2] fails
2. PEEK[..-2] fails
3. PEEK[-2..] fails
4. PEEK[-1] ≡ "item" succeeds
5. PEEK[-1..] ≡ ("item") succeeds
6. PEEK[..-1] ≡ () succeeds