Enhance `#scan_integer` to check for valid character following it

[gettalong]

Recently the new method #scan_integer was introduced (see #113) to optimize scanning integer values.

The current implementation works regardless of what follows the integer, i.e. scanning 123, 123 something, 123,something, 123.32 and 123something all work and would return 123.

However, in - I suspect - many cases an integer may only be a valid integer if it is (not) followed by certain characters. One example is the input 123d which leads to an error when interpreted as Ruby code.

My use case is PDF syntax. There a token is an integer only when it is followed by a whitespace (ASCII decimal 0, 9, 10, 12, 13 and 32) or a delimiter (( ) < > [ ] / %) character (otherwise it is a generic token). To handle this the implementation using #scan_integer looks like this:

    # Parses the number (integer or real) at the current position.
    #
    # See: PDF2.0 s7.3.3
    def parse_number
      prepare_string_scanner(20)
      pos = self.pos
      if (tmp = @ss.scan_integer)
        if @ss.eos? || @ss.match?(WHITESPACE_OR_DELIMITER_RE)
          # Handle object references, see PDF2.0 s7.3.10
          prepare_string_scanner(10)
          if @ss.scan(REFERENCE_RE)
            tmp = if tmp > 0
                    Reference.new(tmp, @ss[1].to_i)
                  else
                    maybe_raise("Invalid indirect object reference (#{tmp},#{@ss[1].to_i})")
                    nil
                  end
          end
          return tmp
        else
          self.pos = pos
        end
      end

      val = scan_until(WHITESPACE_OR_DELIMITER_RE) || @ss.scan(/.*/)
      if val.match?(/\A[+-]?(?:\d+\.\d*|\.\d+)\z/)
        val << '0' if val.getbyte(-1) == 46 # dot '.'
        Float(val)
      else
        TOKEN_CACHE[val] # val is keyword
      end
    end
  end

As you can see we

1. need to store the current scan position,
2. check if scanning an integer works at the current position,
3. scan the content after the integer to verify that it is indeed an integer and work with it, or
4. if the previous step didn't work, reset the scan position.

This could be simplified to just a call of #scan_integer if this method would optionally check the contents after it. Something like #scan_integer(separator: SEPARATOR_PATTERN) or maybe #scan_integer(separator_chars: STRING) (where STRING contains separator characters, similar to whole String#tr works).

Would it make sense to include such functionality?

[kou]

I understand the motivation but I feel that we can find better API for this...

[gettalong]

I'm not sure about the argument name but I think it does make sense to extend the functionality of #scan_integer and not introduce another method like #scan_delimited_integer.

[kou]

Can we process a generic token and then an integer?

token = scanner.scan(/[\da-zA-Z]?[a-zA-Z]/)
return token if token
integer = scanner.scan_integer
return integer if integer

[gettalong]

It is the other way around: The thing at pos might be a number (e.g. 1234) but if that number is directly followed eg. by a letter (e.g. 1234a) it is a token/keyword. So the next step in your example would be to scan for a generic token/keyword again (that's the last else path in my original example).

[kou]

Can we reconstruct the processing order? I feel that parse_number processes a token too.

loop do
  token = scanner.scan(/[\da-zA-Z]?[a-zA-Z]/)
  if token
    process_token(token)
    next
  end
  number = scanner.scan_integer
  if number
    process_number
    next
  end

[gettalong]

For HexaPDF, tokenization starts at #next_token (https://github.com/gettalong/hexapdf/blob/master/lib/hexapdf/tokenizer.rb#L118). There whitespace at point is ignored/parsed and then the sub-processing routine is chosen based on the byte at point. For the bytes 0-9 - + . the #parse_number is invoked and its result returned. So if it turns out that the token at point is not a number, the last step in #parse_number is to return a generic token (i.e. a PDF keyword).

So yes, #parse_number might also return a generic token (keyword). It is not intended as a standalone routine.

With the currently implemented #scan_integer method I can already omit line https://github.com/gettalong/hexapdf/blob/master/lib/hexapdf/tokenizer.rb#L286 and try to parse the token at point as integer. The benefit of #scan_integer in this case is to avoid creating a string when not necessary, i.e. the second line in your last example.

[tenderlove]

Can you use scan_full with a positive lookahead to check if it's a number, then parse the number? You can tell scan_full not to allocate, afaict:

scan = StringScanner.new("123\x12456<789d111")
while !scan.eos?
  if scan.scan_full(/\d+(?=[\x0\x9\x10\x12\x13\x32\(\)<>\[\]\/%]|$)/, false, false)
    p [:INTEGER, scan.scan_integer]
  else
    # generic scanning
  end
end
p scan

(Just a sketch of the code)

[gettalong]

Thanks for the suggestion @tenderlove! I had to look up #scan_full as it is not officially documented but as far as I can tell the invocation is equivalent to calling #match?.

Yes, doing a #match? and then a #scan_integer would be possible. However, I just tested it out and it was massively slower, see below.

Current code:

    def parse_number
      prepare_string_scanner(40)
      pos = self.pos
      if (tmp = @ss.scan_integer)
        if @ss.eos? || @ss.match?(WHITESPACE_OR_DELIMITER_RE)
          # Handle object references, see PDF2.0 s7.3.10
          prepare_string_scanner(10)
          if @ss.scan(REFERENCE_RE)
            tmp = if tmp > 0
                    Reference.new(tmp, @ss[1].to_i)
                  else
                    maybe_raise("Invalid indirect object reference (#{tmp},#{@ss[1].to_i})")
                    nil
                  end
          end
          return tmp
        else
          self.pos = pos
        end
      end

      val = scan_until(WHITESPACE_OR_DELIMITER_RE) || @ss.scan(/.*/)
      if val.match?(/\A[+-]?(?:\d+\.\d*|\.\d+)\z/)
        val << '0' if val.getbyte(-1) == 46 # dot '.'
        Float(val)
      else
        TOKEN_CACHE[val] # val is keyword
      end
    end

Changed using #match? (only the first if changed):

    def parse_number
      prepare_string_scanner(40)
      if @ss.match?(/[+-]?\d+(?=#{WHITESPACE_OR_DELIMITER_RE}|\z)/)
        tmp = @ss.scan_integer

        # Handle object references, see PDF2.0 s7.3.10
        prepare_string_scanner(10)
        if @ss.scan(REFERENCE_RE)
          tmp = if tmp > 0
                  Reference.new(tmp, @ss[1].to_i)
                else
                  maybe_raise("Invalid indirect object reference (#{tmp},#{@ss[1].to_i})")
                  nil
                end
        end
        return tmp
      end

      val = scan_until(WHITESPACE_OR_DELIMITER_RE) || @ss.scan(/.*/)
      if val.match?(/\A[+-]?(?:\d+\.\d*|\.\d+)\z/)
        val << '0' if val.getbyte(-1) == 46 # dot '.'
        Float(val)
      else
        TOKEN_CACHE[val] # val is keyword
      end
    end
  end

Benchmark code using the benchmark-driver gem:

prelude: |
  require 'hexapdf'
  require 'stringio'
  io = StringIO.new('1 0 5 342 93 ctm')
  tok = HexaPDF::Tokenizer.new(io)
  tok1 = HexaPDF::Tok1.new(io)

benchmark:
  num_cur: 'tok.pos = 0; tok.next_token; tok.next_token; tok.next_token; tok.next_token; tok.next_token'
  num_new: 'tok1.pos = 0; tok1.next_token; tok1.next_token; tok1.next_token; tok1.next_token; tok1.next_token'

Result without YJIT on Ruby 3.4.1:

Warming up --------------------------------------
             num_cur   238.144k i/s -    247.698k times in 1.040119s (4.20μs/i)
             num_new    31.549k i/s -     34.452k times in 1.092020s (31.70μs/i)
Calculating -------------------------------------
             num_cur   230.459k i/s -    714.431k times in 3.100031s (4.34μs/i)
             num_new    31.302k i/s -     94.646k times in 3.023659s (31.95μs/i)

Comparison:
             num_cur:    230459.3 i/s
             num_new:     31301.8 i/s - 7.36x  slower

Result with YJIT on Ruby 3.4.1:

Warming up --------------------------------------
             num_cur   466.348k i/s -    473.814k times in 1.016008s (2.14μs/i)
             num_new    35.426k i/s -     38.236k times in 1.079320s (28.23μs/i)
Calculating -------------------------------------
             num_cur   464.428k i/s -      1.399M times in 3.012406s (2.15μs/i)
             num_new    33.769k i/s -    106.277k times in 3.147174s (29.61μs/i)

Comparison:
             num_cur:    464427.8 i/s
             num_new:     33769.0 i/s - 13.75x  slower

[tenderlove]

Yes, doing a #match? and then a #scan_integer would be possible. However, I just tested it out and it was massively slower, see below.

Ah, I understand. I guess scan_integer doesn't need to do a regex match in advance. Storing the position and then optimistically scanning an integer makes sense. I guess it's cheaper to rewind the position (deoptimize) if your assumptions fail than to do a regex and scan an integer. I can understand this pattern might be kind of ugly, but I wonder if it's so common we need a specific API?

In hexapdf's case, it seems like you could do a scan_integer followed by a peek_byte to know whether or not you need to deoptimize. IOW something like:

BYTE_LUT = []
BYTE_LUT[0] = true
BYTE_LUT[9] = true
BYTE_LUT[10] = true
BYTE_LUT[12] = true
BYTE_LUT[13] = true
BYTE_LUT[32] = true
%w( ( ) < > [ ] / % ).each { |x| BYTE_LUT[x.ord] = true }

pos = self.pos
if (tmp = @ss.scan_integer)
  if @ss.eos?
    fast_case(tmp)
  else
    byte = @ss.peek_byte # no allocation
    if BYTE_LUT[byte]
      @ss.scan_byte # no allocation
      fast_case(tmp)
    else
      deoptimize(pos)
      generic_case
    end
  end
else
  generic_case
end

The LUT might be overkill, but it seemed easier than writing the byte range comparisons.

[gettalong]

Thanks for the idea with the lookup table! I have changed the current implementation to use such a lookup table instead of doing @ss.match? as it is 5-10% faster depending on whether YJIT is active.

I guess it's cheaper to rewind the position (deoptimize) if your assumptions fail than to do a regex and scan an integer. I can understand this pattern might be kind of ugly, but I wonder if it's so common we need a specific API?

This is actually the reason for this issue as I think that in many cases an integer will only be an integer if followed (or not followed by) certain characters. If this check can be built into #scan_integer (or a new method like #scan_delimited_integer) the usage would simplify:

if (tmp = @ss.scan_integer(delimiter: "()<>{}/[]% \n\r\0\t\f")
  fast_case
else
  generic_case
end

[tenderlove]

One issue is that I am worried an implementation like what you propose may end up being slower than using a lookup table as in my example. For example you have this code:

loop do
  if (tmp = @ss.scan_integer(delimiter: "()<>{}/[]% \n\r\0\t\f") # new lut each time?
    fast_case
  else
    generic_case
  end
end

The scan_integer implementation would basically do the same thing we're doing with peek_byte. It may or may not convert the delimiter to its own LUT (or possibly do a regex match) but it cannot cache the LUT (or regex) like we are doing in the constant. Recomputing the LUT or regex would not be free (of course).

Thanks for the idea with the lookup table! I have changed the current implementation to use such a lookup table instead of doing @ss.match? as it is 5-10% faster depending on whether YJIT is active.

Great! I haven't seen your implementation, but you could change to something like this:

    if @ss.eos? || BYTE_LUT[@ss.scan_byte] # optimistically scan byte, no allocation
      fast_case(tmp)
    else
      deoptimize(pos)
      generic_case
    end

Since you have to rewind anyway in the deopt case, you could avoid one method call for the fast case.

[gettalong]

That's a good point!

Another idea popped into my mind which, though, might also be a bit slower than your original version but nicer to read:

if (tmp = @ss.scan_integer { @ss.eos? || BYTE_LUT[@ss.scan_byte] })
  fast_case(tmp)
else
  deoptimize(pos)
  generic_case
end

If a block is given to #scan_integer, it is called if scanning the integer is successful. And if the block returns a truthy value, #scan_integer succeeds and otherwise fails.

This allows the user of the method to define their own LUT and still have a somewhat easier to read code flow. However, since a block is invoked there is the block calling overhead.

ps. For HexaPDF I can just use @ss.peek_byte without @ss.scan_byte since afterwards reading that byte is done elsewhere.

[eregon]

I had to look up #scan_full as it is not officially documented

FWIW, for some reason it's documented at https://docs.ruby-lang.org/en/3.3/StringScanner.html#method-i-scan_full
but not at https://docs.ruby-lang.org/en/3.4/StringScanner.html.

---

Regarding the issue topic, IMO match? + a Regexp should be right tool for the job.
In recent benchmarks I have noticed Regexps are really slow on CRuby (e.g. TruffleRuby is 200x faster for matching a Regexp with match?), there are probably a few performance bugs and/or missed opportunities in there.