bug#58937: text-property-search-backward misses one-character regions

bug#58937: text-property-search-backward misses one-character regions

[Nicolas Graner]

In Emacs 29.0.50, when a single character has a text property and you
try to find it with text-property-search-backward, the result
incorrectly includes previous characters without the property.

Example:

(with-current-buffer (generate-new-buffer "test")
  (insert "123456789")
  (put-text-property 3 4 'foo 'bar)
  (goto-char 6)
  (text-property-search-backward 'foo))

The returned value is
  #s(prop-match 1 4 nil)
instead of
  #s(prop-match 3 4 bar)
and the point in the test buffer is moved to position 1 instead of 3.

This incorrect behavior is the same if you replace (goto-char 6) with
(goto-char 5) or any other value greater than 4. However, the result is
correct with (goto-char 4), i.e. when the backward search starts one
position after the target character. This suggests an off-by-one error
in the code.

Hope this helps,
Nicolas

bug#58937: text-property-search-backward misses one-character regions

[Eli Zaretskii]

> From: Nicolas Graner <nicolas@graner.name>
> Date: Tue, 01 Nov 2022 00:20:58 +0100
> 
> (with-current-buffer (generate-new-buffer "test")
>   (insert "123456789")
>   (put-text-property 3 4 'foo 'bar)
>   (goto-char 6)
>   (text-property-search-backward 'foo))
> 
> The returned value is
>   #s(prop-match 1 4 nil)
> instead of
>   #s(prop-match 3 4 bar)
> and the point in the test buffer is moved to position 1 instead of 3.
> 
> This incorrect behavior is the same if you replace (goto-char 6) with
> (goto-char 5) or any other value greater than 4. However, the result is
> correct with (goto-char 4), i.e. when the backward search starts one
> position after the target character. This suggests an off-by-one error
> in the code.

It isn't due to an off-by-one error, AFAICT, it's because search for
changes in text properties starts from character _before_ point.

Please try the patch below and see if it gives good results.

Lars, any comments?

diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
index d11980f..69bbbd2 100644
--- a/lisp/emacs-lisp/text-property-search.el
+++ b/lisp/emacs-lisp/text-property-search.el
@@ -208,8 +208,12 @@ text-property--find-end-backward
                 (goto-char end)
                 (setq ended t)))))
       ;; End this at the first place the property changes value.
-      (setq end (previous-single-property-change
-                 (point) property nil (point-min)))
+      (setq end
+            (if (text-property--match-p
+                 value (get-text-property (1- (point)) property) predicate)
+                (previous-single-property-change (point)
+                                                 property nil (point-min))
+              (point)))
       (goto-char end))
     (make-prop-match :beginning end
                      :end (1+ start)

bug#58937: text-property-search-backward misses one-character regions

[Nicolas Graner]

> Date: Tue, 01 Nov 2022 12:24:49 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> 
> Please try the patch below and see if it gives good results.
> 
> diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
> index d11980f..69bbbd2 100644
> --- a/lisp/emacs-lisp/text-property-search.el
> +++ b/lisp/emacs-lisp/text-property-search.el
> @@ -208,8 +208,12 @@ text-property--find-end-backward
>                  (goto-char end)
>                  (setq ended t)))))
>        ;; End this at the first place the property changes value.
> -      (setq end (previous-single-property-change
> -                 (point) property nil (point-min)))
> +      (setq end
> +            (if (text-property--match-p
> +                 value (get-text-property (1- (point)) property) predicate)
> +                (previous-single-property-change (point)
> +                                                 property nil (point-min))
> +              (point)))
>        (goto-char end))
>      (make-prop-match :beginning end
>                       :end (1+ start)

It fixes the bug in all the cases I've tested so far, but also
introduces a new one:

(with-current-buffer (generate-new-buffer "test")
  (insert "123456789")
  (put-text-property 2 4 'foo 'bar)
  (goto-char 3)
  (text-property-search-backward 'foo nil t))

Debugger entered--Lisp error: (args-out-of-range 0 0)
  get-text-property(0 foo)
  (text-property--match-p value (get-text-property (1- (point)) property) predicate)
  (if (text-property--match-p value (get-text-property (1- (point)) property) predicate) (previous-single-property-change (point) property nil (point-min)) (point))
  (setq end (if (text-property--match-p value (get-text-property (1- (point)) property) predicate) (previous-single-property-change (point) property nil (point-min)) (point)))
  (if (and value (null predicate)) (let ((ended nil)) (while (not ended) (setq end (previous-single-property-change (point) property)) (if (not end) (progn (goto-char (point-min)) (progn (setq end (point)) (setq ended t))) (goto-char (1- end)) (if (text-property--match-p value (get-text-property (point) property) predicate) nil (goto-char end) (setq ended t))))) (setq end (if (text-property--match-p value (get-text-property (1- (point)) property) predicate) (previous-single-property-change (point) property nil (point-min)) (point))) (goto-char end))
  (let (end) (if (and value (null predicate)) (let ((ended nil)) (while (not ended) (setq end (previous-single-property-change (point) property)) (if (not end) (progn (goto-char (point-min)) (progn (setq end ...) (setq ended t))) (goto-char (1- end)) (if (text-property--match-p value (get-text-property ... property) predicate) nil (goto-char end) (setq ended t))))) (setq end (if (text-property--match-p value (get-text-property (1- (point)) property) predicate) (previous-single-property-change (point) property nil (point-min)) (point))) (goto-char end)) (make-prop-match :beginning end :end (1+ start) :value (get-text-property end property)))
  text-property--find-end-backward(1 foo nil t)
  text-property-search-backward(foo nil t)
  (save-current-buffer (set-buffer (generate-new-buffer "test")) (insert "123456789") (put-text-property 2 4 'foo 'bar) (goto-char 3) (text-property-search-backward 'foo nil t))
  eval((save-current-buffer (set-buffer (generate-new-buffer "test")) (insert "123456789") (put-text-property 2 4 'foo 'bar) (goto-char 3) (text-property-search-backward 'foo nil t)) nil)
  elisp--eval-last-sexp(nil)
  eval-last-sexp(nil)

bug#58937: text-property-search-backward misses one-character regions

[Eli Zaretskii]

> From: Nicolas Graner <nicolas@graner.name>
> Cc: larsi@gnus.org, 58937@debbugs.gnu.org
> Date: Tue, 01 Nov 2022 17:48:37 +0100
> 
> > Date: Tue, 01 Nov 2022 12:24:49 +0200
> > From: Eli Zaretskii <eliz@gnu.org>
> > 
> > Please try the patch below and see if it gives good results.
> > 
> > diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
> > index d11980f..69bbbd2 100644
> > --- a/lisp/emacs-lisp/text-property-search.el
> > +++ b/lisp/emacs-lisp/text-property-search.el
> > @@ -208,8 +208,12 @@ text-property--find-end-backward
> >                  (goto-char end)
> >                  (setq ended t)))))
> >        ;; End this at the first place the property changes value.
> > -      (setq end (previous-single-property-change
> > -                 (point) property nil (point-min)))
> > +      (setq end
> > +            (if (text-property--match-p
> > +                 value (get-text-property (1- (point)) property) predicate)
> > +                (previous-single-property-change (point)
> > +                                                 property nil (point-min))
> > +              (point)))
> >        (goto-char end))
> >      (make-prop-match :beginning end
> >                       :end (1+ start)
> 
> It fixes the bug in all the cases I've tested so far, but also
> introduces a new one:
> 
> (with-current-buffer (generate-new-buffer "test")
>   (insert "123456789")
>   (put-text-property 2 4 'foo 'bar)
>   (goto-char 3)
>   (text-property-search-backward 'foo nil t))
> 
> Debugger entered--Lisp error: (args-out-of-range 0 0)
>   get-text-property(0 foo)

Thanks for testing, how about the following patch instead?

diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
index d11980f..f7ef84a 100644
--- a/lisp/emacs-lisp/text-property-search.el
+++ b/lisp/emacs-lisp/text-property-search.el
@@ -208,8 +208,13 @@ text-property--find-end-backward
                 (goto-char end)
                 (setq ended t)))))
       ;; End this at the first place the property changes value.
-      (setq end (previous-single-property-change
-                 (point) property nil (point-min)))
+      (setq end
+            (if (or (= (point) (point-min))
+                    (text-property--match-p
+                     value (get-text-property (1- (point)) property) predicate)
+                    (previous-single-property-change (point)
+                                                     property nil (point-min)))
+              (point)))
       (goto-char end))
     (make-prop-match :beginning end
                      :end (1+ start)

bug#58937: text-property-search-backward misses one-character regions

[Eli Zaretskii]

> From: Nicolas Graner <nicolas@graner.name>
> Cc: larsi@gnus.org, 58937@debbugs.gnu.org
> Date: Tue, 01 Nov 2022 17:48:37 +0100
> 
> > Date: Tue, 01 Nov 2022 12:24:49 +0200
> > From: Eli Zaretskii <eliz@gnu.org>
> > 
> > Please try the patch below and see if it gives good results.
> > 
> > diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
> > index d11980f..69bbbd2 100644
> > --- a/lisp/emacs-lisp/text-property-search.el
> > +++ b/lisp/emacs-lisp/text-property-search.el
> > @@ -208,8 +208,12 @@ text-property--find-end-backward
> >                  (goto-char end)
> >                  (setq ended t)))))
> >        ;; End this at the first place the property changes value.
> > -      (setq end (previous-single-property-change
> > -                 (point) property nil (point-min)))
> > +      (setq end
> > +            (if (text-property--match-p
> > +                 value (get-text-property (1- (point)) property) predicate)
> > +                (previous-single-property-change (point)
> > +                                                 property nil (point-min))
> > +              (point)))
> >        (goto-char end))
> >      (make-prop-match :beginning end
> >                       :end (1+ start)
> 
> It fixes the bug in all the cases I've tested so far, but also
> introduces a new one:
> 
> (with-current-buffer (generate-new-buffer "test")
>   (insert "123456789")
>   (put-text-property 2 4 'foo 'bar)
>   (goto-char 3)
>   (text-property-search-backward 'foo nil t))
> 
> Debugger entered--Lisp error: (args-out-of-range 0 0)
>   get-text-property(0 foo)

Sorry, please disregard the previous message and use the patch below
instead:

diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
index d11980f..1e7f346 100644
--- a/lisp/emacs-lisp/text-property-search.el
+++ b/lisp/emacs-lisp/text-property-search.el
@@ -208,8 +208,13 @@ text-property--find-end-backward
                 (goto-char end)
                 (setq ended t)))))
       ;; End this at the first place the property changes value.
-      (setq end (previous-single-property-change
-                 (point) property nil (point-min)))
+      (setq end
+            (if (and (> (point) (point-min))
+                     (text-property--match-p
+                      value (get-text-property (1- (point)) property) predicate)
+                     (previous-single-property-change (point)
+                                                      property nil (point-min)))
+                (point)))
       (goto-char end))
     (make-prop-match :beginning end
                      :end (1+ start)

bug#58937: text-property-search-backward misses one-character regions

[Eli Zaretskii]

> Date: Tue, 01 Nov 2022 19:00:28 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: larsi@gnus.org, 58937@debbugs.gnu.org
> 
> > From: Nicolas Graner <nicolas@graner.name>
> > Cc: larsi@gnus.org, 58937@debbugs.gnu.org
> > Date: Tue, 01 Nov 2022 17:48:37 +0100
> > 
> > > Date: Tue, 01 Nov 2022 12:24:49 +0200
> > > From: Eli Zaretskii <eliz@gnu.org>
> > > 
> > > Please try the patch below and see if it gives good results.
> > > 
> > > diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
> > > index d11980f..69bbbd2 100644
> > > --- a/lisp/emacs-lisp/text-property-search.el
> > > +++ b/lisp/emacs-lisp/text-property-search.el
> > > @@ -208,8 +208,12 @@ text-property--find-end-backward
> > >                  (goto-char end)
> > >                  (setq ended t)))))
> > >        ;; End this at the first place the property changes value.
> > > -      (setq end (previous-single-property-change
> > > -                 (point) property nil (point-min)))
> > > +      (setq end
> > > +            (if (text-property--match-p
> > > +                 value (get-text-property (1- (point)) property) predicate)
> > > +                (previous-single-property-change (point)
> > > +                                                 property nil (point-min))
> > > +              (point)))
> > >        (goto-char end))
> > >      (make-prop-match :beginning end
> > >                       :end (1+ start)
> > 
> > It fixes the bug in all the cases I've tested so far, but also
> > introduces a new one:
> > 
> > (with-current-buffer (generate-new-buffer "test")
> >   (insert "123456789")
> >   (put-text-property 2 4 'foo 'bar)
> >   (goto-char 3)
> >   (text-property-search-backward 'foo nil t))
> > 
> > Debugger entered--Lisp error: (args-out-of-range 0 0)
> >   get-text-property(0 foo)
> 
> Sorry, please disregard the previous message and use the patch below
> instead:

Not my best day, I guess.  Please use this patch instead of the
previous two:

diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
index d11980f..d41222b 100644
--- a/lisp/emacs-lisp/text-property-search.el
+++ b/lisp/emacs-lisp/text-property-search.el
@@ -208,8 +208,14 @@ text-property--find-end-backward
                 (goto-char end)
                 (setq ended t)))))
       ;; End this at the first place the property changes value.
-      (setq end (previous-single-property-change
-                 (point) property nil (point-min)))
+      (setq end
+            (if (and (> (point) (point-min))
+                     (text-property--match-p
+                      value (get-text-property (1- (point)) property)
+                      predicate))
+                (previous-single-property-change (point)
+                                                 property nil (point-min))
+              (point)))
       (goto-char end))
     (make-prop-match :beginning end
                      :end (1+ start)

bug#58937: text-property-search-backward misses one-character regions

[Nicolas Graner]

> Date: Tue, 01 Nov 2022 19:05:41 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> To: nicolas@graner.name
> CC: larsi@gnus.org, 58937@debbugs.gnu.org

> diff --git a/lisp/emacs-lisp/text-property-search.el b/lisp/emacs-lisp/text-property-search.el
> index d11980f..d41222b 100644
> --- a/lisp/emacs-lisp/text-property-search.el
> +++ b/lisp/emacs-lisp/text-property-search.el
> @@ -208,8 +208,14 @@ text-property--find-end-backward
>                  (goto-char end)
>                  (setq ended t)))))
>        ;; End this at the first place the property changes value.
> -      (setq end (previous-single-property-change
> -                 (point) property nil (point-min)))
> +      (setq end
> +            (if (and (> (point) (point-min))
> +                     (text-property--match-p
> +                      value (get-text-property (1- (point)) property)
> +                      predicate))
> +                (previous-single-property-change (point)
> +                                                 property nil (point-min))
> +              (point)))
>        (goto-char end))
>      (make-prop-match :beginning end

This works fine in all the cases I have tested, although I don't claim
to have tested all relevant combinations of arguments and region lengths
and positions...

In the process, I think I uncovered another bug common to
text-property-search-forward and -backward. Before filing a bug report
I'd like to make sure my understanding is correct. It may also be a
documentation error.

Here, the PREDICATE argument is a function, not the usual t or nil:

(with-current-buffer (generate-new-buffer "test")
  (insert "123456789")
  (put-text-property 2 4 'foo "abcd")
  (put-text-property 4 6 'foo "efgh")
  (goto-char 1)
  (text-property-search-forward 'foo 4 (lambda (l str) (= l (length str)))))

This returns:
#s(prop-match 2 4 "abcd")
but I think it should be:
#s(prop-match 2 6 "abcd")
since both the (2 4) and the (4 6) regions satisfy the predicate.

The docstring for text-property-search-forward says:
    If PREDICATE is nil (which is the default value), a value will
    match if is not ‘equal’ to VALUE.  Furthermore, a nil PREDICATE
    means that the match region is ended if the value changes.

This implies that when PREDICATE is not nil, the match region should not
end when the value changes, but only when the predicate is no longer
satisfied. Is this correct?

Nicolas

bug#58937: text-property-search-backward misses one-character regions

[Eli Zaretskii]

> From: Nicolas Graner <nicolas@graner.name>
> Cc: larsi@gnus.org, 58937@debbugs.gnu.org
> Date: Thu, 03 Nov 2022 00:40:43 +0100
> 
> This works fine in all the cases I have tested, although I don't claim
> to have tested all relevant combinations of arguments and region lengths
> and positions...

Thanks, I installed the change.

> Here, the PREDICATE argument is a function, not the usual t or nil:
> 
> (with-current-buffer (generate-new-buffer "test")
>   (insert "123456789")
>   (put-text-property 2 4 'foo "abcd")
>   (put-text-property 4 6 'foo "efgh")
>   (goto-char 1)
>   (text-property-search-forward 'foo 4 (lambda (l str) (= l (length str)))))

??? The documentation says PREDICATE is called with 2 arguments: the
VALUE argument to text-property-search-forward and the actual value of
the text property to examine.  There's no property value of 4 in this
example, so it sounds like you are (ab)using the feature in some way
that we didn't really intend to support.

More to the point, Emacs always considers segments of characters whose
values of the same property are different as distinct segments.  You
seem to expect that Emacs would join these two segments because you
supplied PREDICATE that returns t for both, but Emacs cannot do that,
because the underlying text-property machinery doesn't even look at
the next segment before it processes the first one.  And no PREDICATE
in this API can ever change that basic fact.

So your expectations are incorrect, and cannot be met by this API,
which specifically meant to examine the text segments one by one and
subject each one of them to PREDICATE, separately.

> The docstring for text-property-search-forward says:
>     If PREDICATE is nil (which is the default value), a value will
>     match if is not ‘equal’ to VALUE.  Furthermore, a nil PREDICATE
>     means that the match region is ended if the value changes.
> 
> This implies that when PREDICATE is not nil, the match region should not
> end when the value changes, but only when the predicate is no longer
> satisfied. Is this correct?

No, it isn't.  The region always ends where the property changes
value, regardless of what PREDICATE thinks.