Searching for line beginning

Searching for line beginning

[Eli Zaretskii]

C-a (move-beginning-of-line) does this to find the line's beginning:

    ;; Move to beginning-of-line, ignoring fields and invisible text.
    (skip-chars-backward "^\n")
    (while (and (not (bobp)) (invisible-p (1- (point))))
      (goto-char (previous-char-property-change (point)))
      (skip-chars-backward "^\n"))

Apart of the fields part (which can be handled by binding
inhibit-field-text-motion), can anyone see a reason why not use
line-beginning-position instead?  The latter is much faster,
especially when lines are very long.

Re: Searching for line beginning

[Stefan Monnier]

Eli Zaretskii [2022-08-13 18:43:29] wrote:

> C-a (move-beginning-of-line) does this to find the line's beginning:
>
>     ;; Move to beginning-of-line, ignoring fields and invisible text.
>     (skip-chars-backward "^\n")
>     (while (and (not (bobp)) (invisible-p (1- (point))))
>       (goto-char (previous-char-property-change (point)))
>       (skip-chars-backward "^\n"))
>
> Apart of the fields part (which can be handled by binding
> inhibit-field-text-motion), can anyone see a reason why not use
> line-beginning-position instead?  The latter is much faster,
> especially when lines are very long.

You mean instead of `skip-chars-backward`?  I can't see a reason, no.


        Stefan

Re: Searching for line beginning

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Sat, 13 Aug 2022 12:20:04 -0400
> 
> Eli Zaretskii [2022-08-13 18:43:29] wrote:
> 
> > C-a (move-beginning-of-line) does this to find the line's beginning:
> >
> >     ;; Move to beginning-of-line, ignoring fields and invisible text.
> >     (skip-chars-backward "^\n")
> >     (while (and (not (bobp)) (invisible-p (1- (point))))
> >       (goto-char (previous-char-property-change (point)))
> >       (skip-chars-backward "^\n"))
> >
> > Apart of the fields part (which can be handled by binding
> > inhibit-field-text-motion), can anyone see a reason why not use
> > line-beginning-position instead?  The latter is much faster,
> > especially when lines are very long.
> 
> You mean instead of `skip-chars-backward`?

Yes.

> I can't see a reason, no.

Thanks for the feedback.

Re: Searching for line beginning

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Sat, 13 Aug 2022 12:20:04 -0400
> 
> Eli Zaretskii [2022-08-13 18:43:29] wrote:
> 
> > C-a (move-beginning-of-line) does this to find the line's beginning:
> >
> >     ;; Move to beginning-of-line, ignoring fields and invisible text.
> >     (skip-chars-backward "^\n")
> >     (while (and (not (bobp)) (invisible-p (1- (point))))
> >       (goto-char (previous-char-property-change (point)))
> >       (skip-chars-backward "^\n"))
> >
> > Apart of the fields part (which can be handled by binding
> > inhibit-field-text-motion), can anyone see a reason why not use
> > line-beginning-position instead?  The latter is much faster,
> > especially when lines are very long.
> 
> You mean instead of `skip-chars-backward`?  I can't see a reason, no.

Done.

Re: Searching for line beginning

[Basil L. Contovounesios]

Eli Zaretskii [2022-08-13 18:43 +0300] wrote:

> C-a (move-beginning-of-line) does this to find the line's beginning:
>
>     ;; Move to beginning-of-line, ignoring fields and invisible text.
>     (skip-chars-backward "^\n")
>     (while (and (not (bobp)) (invisible-p (1- (point))))
>       (goto-char (previous-char-property-change (point)))
>       (skip-chars-backward "^\n"))
>
> Apart of the fields part (which can be handled by binding
> inhibit-field-text-motion), can anyone see a reason why not use
> line-beginning-position instead?  The latter is much faster,
> especially when lines are very long.

FWIW, one could also say (beginning-of-line) or (beginning-of-line 1)
instead of (goto-char (line-beginning-position)).  But they boil down to
the same thing, so they should be very close in terms of performance.

Thanks,

-- 
Basil

Re: Searching for line beginning

[Eli Zaretskii]

> From: "Basil L. Contovounesios" <contovob@tcd.ie>
> Cc: emacs-devel@gnu.org
> Date: Sun, 14 Aug 2022 18:33:00 +0300
> 
> Eli Zaretskii [2022-08-13 18:43 +0300] wrote:
> 
> > C-a (move-beginning-of-line) does this to find the line's beginning:
> >
> >     ;; Move to beginning-of-line, ignoring fields and invisible text.
> >     (skip-chars-backward "^\n")
> >     (while (and (not (bobp)) (invisible-p (1- (point))))
> >       (goto-char (previous-char-property-change (point)))
> >       (skip-chars-backward "^\n"))
> >
> > Apart of the fields part (which can be handled by binding
> > inhibit-field-text-motion), can anyone see a reason why not use
> > line-beginning-position instead?  The latter is much faster,
> > especially when lines are very long.
> 
> FWIW, one could also say (beginning-of-line) or (beginning-of-line 1)
> instead of (goto-char (line-beginning-position)).

As a matter of principle, I don't like calling commands from Lisp if I
can avoid that, because commands frequently have extensive checks of
the arguments that are redundant in non-interactive calls.

Re: Searching for line beginning

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

>> FWIW, one could also say (beginning-of-line) or (beginning-of-line 1)
>> instead of (goto-char (line-beginning-position)).
>
> As a matter of principle, I don't like calling commands from Lisp if I
> can avoid that, because commands frequently have extensive checks of
> the arguments that are redundant in non-interactive calls.

`goto-char' is also a command, though.

Re: Searching for line beginning

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: "Basil L. Contovounesios" <contovob@tcd.ie>,  emacs-devel@gnu.org
> Date: Sun, 14 Aug 2022 17:43:38 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> FWIW, one could also say (beginning-of-line) or (beginning-of-line 1)
> >> instead of (goto-char (line-beginning-position)).
> >
> > As a matter of principle, I don't like calling commands from Lisp if I
> > can avoid that, because commands frequently have extensive checks of
> > the arguments that are redundant in non-interactive calls.
> 
> `goto-char' is also a command, though.

No one is perfect.

Re: Searching for line beginning

[Stefan Monnier]

Eli Zaretskii [2022-08-14 18:36:52] wrote:
>> From: "Basil L. Contovounesios" <contovob@tcd.ie>
>> Cc: emacs-devel@gnu.org
>> Date: Sun, 14 Aug 2022 18:33:00 +0300
>> 
>> Eli Zaretskii [2022-08-13 18:43 +0300] wrote:
>> 
>> > C-a (move-beginning-of-line) does this to find the line's beginning:
>> >
>> >     ;; Move to beginning-of-line, ignoring fields and invisible text.
>> >     (skip-chars-backward "^\n")
>> >     (while (and (not (bobp)) (invisible-p (1- (point))))
>> >       (goto-char (previous-char-property-change (point)))
>> >       (skip-chars-backward "^\n"))
>> >
>> > Apart of the fields part (which can be handled by binding
>> > inhibit-field-text-motion), can anyone see a reason why not use
>> > line-beginning-position instead?  The latter is much faster,
>> > especially when lines are very long.
>> 
>> FWIW, one could also say (beginning-of-line) or (beginning-of-line 1)
>> instead of (goto-char (line-beginning-position)).
>
> As a matter of principle, I don't like calling commands from Lisp if I
> can avoid that, because commands frequently have extensive checks of
> the arguments that are redundant in non-interactive calls.

I also like to avoid moving point when it's possible/easy (my original
motivation was to avoid the extra tricky semantics of moving point in
the presence of things like `point-entered` and `intangible` properties,
but even with `inhibit-point-motion-hooks` permanently set to t I think
it's preferable not to move point when given the choice).

In the above loop, it seems it's easy not to move point.


        Stefan

Re: Searching for line beginning

[Lars Ingebrigtsen]

By the way, I see that Fline_beginning_position/end have grown field
capabilities while I wasn't looking (in 2000).  I.e., they call
Fconstrain_to_field, which is a pretty complex function.  This means
that rewriting a loop like

  (let ((sum 0))
    (goto-char (point-min))
    (while (not (eobp))
      (goto-char (line-end-position))
      (setq sum (+ sum (point)))
      (forward-char 1))
    sum)

into

  (let ((sum 0))
    (goto-char (point-min))
    (while (not (eobp))
      (forward-line 1)
      (setq sum (+ sum (1- (point)))))
    sum)

is more than twice as fast, which is sad.  (Because `forward-line'
doesn't do the field stuff.)

The field stuff only makes sense in user-oriented buffers, while we use
line-end-position extensively in Emacs to parse buffers in general --
but we get this field penalty throughout Emacs.

Re: Searching for line beginning

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: contovob@tcd.ie,  emacs-devel@gnu.org
> Date: Mon, 15 Aug 2022 06:28:05 +0200
> 
> By the way, I see that Fline_beginning_position/end have grown field
> capabilities while I wasn't looking (in 2000).  I.e., they call
> Fconstrain_to_field, which is a pretty complex function.

You can disable that by binding inhibit-field-text-motion.

> The field stuff only makes sense in user-oriented buffers, while we use
> line-end-position extensively in Emacs to parse buffers in general --
> but we get this field penalty throughout Emacs.

line-beginning-position is also needed in handling UI, so it needs to
serve double duty.  If the application doesn't need to cater to
fields, it can disable that, see above.

Re: Searching for line beginning

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> You can disable that by binding inhibit-field-text-motion.

I know, but nobody does that.  (And it's still 40% slower than
`forward-line' -- but that can be fixed by checking for that earlier
instead of always calling Fconstrain_to_field.)

> line-beginning-position is also needed in handling UI, so it needs to
> serve double duty.  If the application doesn't need to cater to
> fields, it can disable that, see above.

If we want to fix this, I think we should just introduce two new
functions for "real" bol/eol, because this is already awkward enough.

Re: Searching for line beginning

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: contovob@tcd.ie,  emacs-devel@gnu.org
> Date: Mon, 15 Aug 2022 13:37:56 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> If we want to fix this, I think we should just introduce two new
> functions for "real" bol/eol, because this is already awkward enough.

I won't object.

Re: Searching for line beginning

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > > If we want to fix this, I think we should just introduce two new
  > > functions for "real" bol/eol, because this is already awkward enough.

  > I won't object.

What would these new functions do?  How would they be different from
bolp and eolp?

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Searching for line beginning

[Lars Ingebrigtsen]

Richard Stallman <rms@gnu.org> writes:

>   > > If we want to fix this, I think we should just introduce two new
>   > > functions for "real" bol/eol, because this is already awkward enough.
>
>   > I won't object.
>
> What would these new functions do?  How would they be different from
> bolp and eolp?

They'd be alternatives to line-end-position/line-beginning-position, not
bolp/eolp.

Re: Searching for line beginning

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> Cc: larsi@gnus.org, contovob@tcd.ie, emacs-devel@gnu.org
> Date: Tue, 16 Aug 2022 22:49:26 -0400
> 
>   > > If we want to fix this, I think we should just introduce two new
>   > > functions for "real" bol/eol, because this is already awkward enough.
> 
>   > I won't object.
> 
> What would these new functions do?  How would they be different from
> bolp and eolp?

bolp and eolp don't _search_ for next/previous newline, they just
report if point already _is_ at or before a newline.

The intent is to have a function similar to line-beginning-position,
but without the stuff that accounts for fields.

Re: Searching for line beginning

[Stefan Monnier]

>> line-beginning-position is also needed in handling UI, so it needs to
>> serve double duty.  If the application doesn't need to cater to
>> fields, it can disable that, see above.
> If we want to fix this, I think we should just introduce two new
> functions for "real" bol/eol, because this is already awkward enough.

How 'bout adding an optional argument?


        Stefan

Re: Searching for line beginning

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> How 'bout adding an optional argument?

That's also an option, but there's already an optional parameter here,
so we'd end up with

  (buffer-substring (line-beginning-position nil t) (line-end-position nil t))

etc all over the place, which is a mouthful to both type and read.

I've done some grepping and reading code in the Emacs code base to
broadly guesstimate how much code means "give me a line" when they say
"give me a line" (as opposed to a field), and I think it's basically
most.  So I think just adding a new function name for the behaviour most
code is looking for would be a better long time solution.

I was also wondering how much the optional N argument is used (because I
wondered whether the new function should perhaps be N-less, because the
N value isn't intuitive -- -1 and 1 aren't symmetric), and it's a lot
more than I would have guessed -- about a third of the calls have a
non-nil/non-1 N.  Like:

	  ;; Insert the entries just found.
	  (while (= (line-beginning-position 0) (1- (point)))
	    (backward-char))

and

              (insert "\n")
              (put-text-property
               (line-beginning-position 0) (line-beginning-position)
               'mpc-file (mpc-songs-hashcons (cdr (assq 'file song))))

and

    (narrow-to-region (line-beginning-position)
                      (line-beginning-position 2))

Now, some of these are just bad code (or were written before
`propertize' existed), but the N will stay in the new function (if
added).