Netstring parser in common lisp

Question

Below is a netstring parser I wrote in Common Lisp. The docstring contains the usage and return.

(defun parse-netstring (netstring acc)
  "recursively parses netstring of the form
   size1:string1,size2:string2,size3:string3,
   acc can be any list, or nil
   returns -> (string3 string2 string1)"
  (if (equalp netstring "")
      acc
      (let* ((netstring-split
          (split-on-first-char #\: netstring))
         (comma-index
          (parse-integer (first netstring-split)))
         (netstring-body
          (second netstring-split)))
    (if (not (char= #\, (aref netstring-body comma-index)))
      (error 'malformed-netstring-error :netstring netstring)
      (parse-netstring
       (subseq netstring-body (1+ comma-index))
       (cons (subseq netstring-body 0 comma-index) acc))))))

Answer 1

First a few minor points:

1. You should give the definition of split-on-first-char since it is an important function in this context.

2. You should use equal instead of equalp to compare a value with a string (assuming that you cannot use string= to allow the first argument not to be a string).

3. The second parameter of parse-netstring could be defined as &optional, so that the function could be called with only the first parameter, and the second is automatically initialized with the empty list.

Then, let’s go to the main point: your function does not check many error conditions, and this is very bad for a function like this, that could get its input from the outside of the system (for instance, from a stream or a file). So, I think that you should do much more checks, for instance:

1. when the string does not start with a number,

2. when the first string part is less than the size,

3. when the size is greater than the whole string, etc.

The objective is to catch all the possible errors arising from calling primitive functions.

So I propose to rewrite the function in the following way, and in rewriting it I propose also a different approach to the recursion: use an auxiliary function, and recur only on the start index of the string, this make the code simpler and avoid a lot of costly subseq calls. Moreover, working with the indexes allow to get rid of the function split-on-first-char (again, with costly subseq calls). This is made possible also by the use of parse-integer with the junk-allowed parameter, which stops on the first non-numeric character, and by the fact that parse-integer returns two values, the number (which is NIL if it is not present), and the first position after the number. Here is the function:

(defun parse-netstring (netstring &optional acc)
  "recursively parses netstring of the form
   size1:string1,size2:string2,size3:string3,
   acc can be any list, or nil
   returns -> (string3 string2 string1)"
  (check-type netstring string "a string")
  (check-type acc list "a list")
  (let ((end (length netstring)))
    (labels ((parse-aux (start acc)
               (if (= start end)
                   acc
                   (multiple-value-bind (string-size semicolon-position)
                       (parse-integer netstring :start start :junk-allowed t)
                     (let ((comma-position
                             (when string-size (+ string-size semicolon-position 1))))
                       (unless (and string-size
                                    (< comma-position end)
                                    (<= string-size end)
                                    (char= (char netstring semicolon-position) #\:)
                                    (char= (char netstring comma-position) #\,))
                         (error  'malformed-netstring-error :netstring netstring))
                       (parse-aux 
                         (1+ comma-position) 
                         (cons (subseq netstring (1+ semicolon-position) comma-position) acc)))))))
      (parse-aux 0 acc))))

Answer 2

• Common Lisp allows to work directly from the input string, without the need to create intermediate sub-sequences. We need to keep an index into the string. Many string/sequence related functions allow :start and :end parameters, to limit the range.
• Recursion might have problems with a limited stack depth. For portable and efficient code, loops might be better.

Function PARSE-NETSTRING:

(defun parse-netstring (string &aux (string-length (length string)))
  (when (plusp string-length)
    (loop for start = 0 then (+ end-pos 1)
          for colon-pos = (position #\: string :start start)
          for length    = (if colon-pos
                              (parse-integer string :start start :end colon-pos)
                            (error "Colon missing after ~a in \"~a\""
                                   start string))
          for end-pos   = (when length                            
                            (+ colon-pos length 1))
          for sstring   = (when end-pos
                            (when (> end-pos string-length)
                              (error "Wrong substring size ~a in \"~a\""
                                   length string))
                            (subseq string (1+ colon-pos) end-pos))
          collect sstring
          while (and colon-pos
                     end-pos
                     (< (+ end-pos 1) string-length)))))

Answer 3

OK, here are my two cents:

1. netstring is about bytes, but you are working with strings. In CL strings are made of characters, not bytes (a.k.a. octets). I.e. they are sequences of a different type.
2. The idea of netstring format is that one can read it from stream: the reader should be able to read records as they are added to the stream. In practical situations these may be coming from network or being generated by another program, so the idea of working with strings or vectors will not hold water: you need to be using streams. Streams do exist in CL, but... binary streams are problematic (read non-existent) if you use vanilla CL. However, flexi-streams library provides portable implementations.
3. Arguably, it would've been better to split parsing into several routines, which are easier to test in separation. This is really a matter of taste: some prefer very short functions, some don't like the proliferation of small functions...

Anyways, below is an attempt at reimplementing it with above ideas in mind:

(defpackage :doodles (:use :cl :iterate :flexi-streams))
(in-package :doodles)

(defun read-num (stream)
  (iter
    (for b := (read-byte stream nil nil))
    (while b)
    (let ((d (code-char b)))
      (cond
        ((digit-char-p d) (collect d :into digits))
        ((char= #\: (code-char b))
         (return (parse-integer (coerce digits 'string))))
        (t (error "Unexpected character at ~d: ~c"
                  (file-position stream) (code-char b)))))))

(defun read-str (stream n)
  (prog1
      (let ((str (make-array n :element-type 'octet)))
        (read-sequence str stream)
        (octets-to-string str))
    (let ((b (read-byte stream)))
      (unless (char= (code-char b) #\,)
        (error "Expected comma at ~d, but found ~c"
               (file-position stream) (code-char b))))))

(defun decode-netstring-stream (stream)
  (iter
    (for n := (read-num stream))
    (while n)
    (for s := (read-str stream n))
    (collect s)))

(defun test-decode-netstring-stream (str)
  (decode-netstring-stream
   (make-in-memory-input-stream (string-to-octets str))))