Balland optimiser incorrectly fuses patterns for strings of the same length

[4dplanner]

Hello! When using the Balland optimizer, using multiple (equals str) patterns for strings of the same length will mask all patterns except the first. This does not occur with the trivial optimizer (see below)

Git commit hash: 8b406c3f83521d290e97bb787d3f6c1eb3b716af

Org mode file to reproduce:

These patterns have the same inferred type (string of length 3), but represent different values.

Balland optimizer:
#+BEGIN_SRC lisp
    (defun balland-error ()
      (declare (trivia:optimizer :balland2006))
      (trivia:match "foo"
        ((equal "bar") "We matched bar incorrectly.")
        ((equal "foo") "We matched foo, as expected.")
        (otherwise "We didn't match the value!")))
    (balland-error)
#+END_SRC

#+RESULTS:
: We didn't match the value!

Trivial optimizer:
#+BEGIN_SRC lisp
  (defun trivial-works ()
    (declare (trivia:optimizer :trivial))
    (trivia:match "foo"
        ((equal "bar") "We matched bar incorrectly.")
        ((equal "foo") "We matched foo, as expected.")
        (otherwise "We didn't match the value!")))
  (trivial-works)
#+END_SRC

#+RESULTS:
: We matched foo, as expected.

[guicho271828]

Thanks for the bug report. Can you show me the result of macro expansion?

[4dplanner]

Macro expansion goes normally until

(TRIVIA.LEVEL2:MATCH2*+ ("foo")
      (T)
    (((EQUAL "bar")) "We matched bar incorrectly.")
    (((EQUAL "foo")) "We matched foo, as expected.")
    ((OTHERWISE) "We didn't match the value!")
    ((TRIVIA.LEVEL2.IMPL::_) NIL))

Then the expansion involving fusion produces this incorrect result:

(SYMBOL-MACROLET ((#:ARG880 "foo"))
    (DECLARE)
    (TRIVIA.LEVEL1:MATCH1 #:ARG880
      ((TRIVIA.LEVEL1:GUARD1 (#:FUSION885 :TYPE (SIMPLE-ARRAY CHARACTER (3)))
        (EQUAL #:FUSION885 "bar") #:FUSION885
        (TRIVIA.LEVEL1:GUARD1 (#:IT881 :TYPE (SIMPLE-ARRAY CHARACTER (3))) T)
        #:FUSION885
        (TRIVIA.LEVEL1:GUARD1 (#:IT882 :TYPE (SIMPLE-ARRAY CHARACTER (3))) T))
       (TRIVIA.LEVEL1:MATCH1 NIL
         ((TRIVIA.LEVEL1:GUARD1 #:IT888 T)
          (TRIVIA.LEVEL2:MATCH2*+ NIL
              NIL
            (NIL "We matched bar incorrectly.")
            (NIL "We matched foo, as expected.")
            (TRIVIA.BALLAND2006::_ (TRIVIA.SKIP:SKIP))))
         ((TRIVIA.LEVEL1:GUARD1 #:IT889 T) (TRIVIA.NEXT:NEXT))))
      ((TRIVIA.LEVEL1:GUARD1
        (#:IT883 :SPECIAL NIL :DYNAMIC-EXTENT NIL :IGNORABLE T :BINDER LET :TYPE
         T)
        T)
       (TRIVIA.LEVEL1:MATCH1 NIL
         ((TRIVIA.LEVEL1:GUARD1 #:IT890 T) "We didn't match the value!")
         ((TRIVIA.LEVEL1:GUARD1 #:IT891 T) (TRIVIA.NEXT:NEXT))))
      ((TRIVIA.LEVEL1:GUARD1
        (#:IT884 :SPECIAL NIL :DYNAMIC-EXTENT NIL :IGNORABLE T :BINDER LET :TYPE
         T)
        T)
       (TRIVIA.LEVEL1:MATCH1 NIL
         ((TRIVIA.LEVEL1:GUARD1 #:IT892 T) NIL)))))

[guicho271828]

reproduced

[guicho271828]

This was due to the wrong type inference rule in type-i that incorrectly relaxed (typep ? [type]) from (equalp ? [type]). These rules should not produce a form that matches a superset.

Thanks for the report! This is a very subtle error that was not captured.

[guicho271828]

(it is subtle because the use of equal rule was rarer.)

[4dplanner]

thank you very much for the fix! do you take donations?

[guicho271828]

I never thought about it