Char-folding: how can we implement matching multiple characters as a single "thing"?

Char-folding: how can we implement matching multiple characters as a single "thing"?

[Artur Malabarba]

I pushed this feature a couple of days ago, but I had to disable it
now (the code is in `character-fold-to-regexp').

For those who don't know, the way char-folding works is by replacing
each character in the search string with a regexp of the characters it
can match.
For instance, a character-folding search for "fi" is actually a regexp
search for "\\(?:ḟ\\|[fᶠḟⓕｆ𝐟𝑓𝒇𝒻𝓯𝔣𝕗𝖋𝖿𝗳𝘧𝙛𝚏]\\)\\(?:i[̀-̨̣̰̄̆̈̉̌̏̑]\\|[iì-ïĩīĭįǐȉȋᵢḭỉịⁱℹⅈⅰⓘｉ𝐢𝑖𝒊𝒾𝓲𝔦𝕚𝖎𝗂𝗶𝘪𝙞𝚒]\\)".

As you can see, this multiplies the length of the string by a factor
of about 45. But that's still acceptable.

However, this only includes foldings for the 'f' character and the 'i'
character independently. As it happens, the string "fi" can also match
the ligature 'fi'.
Now, for the sake of conciseness, let me denote the f and i regexps
above as [f] and [i].

The code I pushed a couple of days ago added support for multi-char
matches (such as "fi" matching that ligature), but returning a regexp
like this: "\\([f][i]\\|fi\\)"
This might not look like much. It only adds a few chars to a regexp
that already has about 90. But the problem is that it introduces a new
branch.

Let's say we want to search for the word "fix". The letters 'i' and
'x' could also represent the character 'ⅸ' (roman numeral nine). So
the only way to write that regexp is:
"\\([f]\\([i][x]\\|ⅸ\\)\\|fi[x]\\)".
Now the pattern [x] (which I remind you has ~ 40 chars) appears twice
in the regexp, and we've gained another branch. If the next character
the search string can also combine with 'x', then we go from 3 to 5
branches.

As you can see. The number of branches will scale badly with the
number of input characters. Which means the number of output
characters will be much more than 40 times the input.
And even if the next character does NOT combine with 'x', it's hard to
write an algorithm that can identify that and close all branches
before continuing with the conversion.

And that is why I disabled this code for now. With a short string like
"endless-visit-notifications" it was return regexps longer than 10k
characters. Which is more than Emacs handle.

Does anyone have alternative ideas?

Re: Char-folding: how can we implement matching multiple characters as a single "thing"?

[Paul Eggert]

On 11/30/2015 07:54 AM, Artur Malabarba wrote:
> Does anyone have alternative ideas?

Sure, scan the pattern greedily for possible sequences, left-to-right.  
In your example "fix" should expand to the regexp "\\([f][i]\\|fi\\)x" 
(where the "fi" is the ligature character), because once the "fi" is 
found, the scanner won't look for "ix" as a single character. This 
should cause the regexp to grow only polynomially rather than 
exponentially. The polynomial version won't match as many strings as the 
exponential version, but in practice it should be good enough.

Re: Char-folding: how can we implement matching multiple characters as a single "thing"?

[Clément Pit--Claudel]

[-- Attachment #1: Type: text/plain, Size: 2706 bytes --]

On 11/30/2015 04:54 PM, Artur Malabarba wrote:
> As you can see. The number of branches will scale badly with the 
> number of input characters. Which means the number of output 
> characters will be much more than 40 times the input. And even if
> the next character does NOT combine with 'x', it's hard to write an 
> algorithm that can identify that and close all branches before 
> continuing with the conversion.
> 
> And that is why I disabled this code for now. With a short string 
> like "endless-visit-notifications" it was return regexps longer than 
> 10k characters. Which is more than Emacs handle.

Hi Arthur,

Thanks for your efforts on this; it would be very convenient for "ff" or "fi" to match their ligature counterparts.

Are the difficulties due to the sheer size of the regular expressions, or to their complexity (too much branching?). If the size is the real issue (and if that size mostly comes from repeated folding of individual characters), then I can think of two options:

* Extend the C-level implementation of regular expressions to make character-folding a capability of the C engine, allowing for succinct regexps + a flag.
* Add a new backslash to regular expressions for matching char-folded characters (custom character categories almost already allow for this, so the implementation would probably be similar).

These two solutions would not help with the branching, but they would allow for smaller input to the regexp engine (again, assuming that the size issue is due to the large brackets, not to the branching).

On the other hand, if excessive branching is the issue (either due to the size of the regexps even with the ideas above applied, or because the engine has trouble with all the backtracking), then maybe normalization can help: instead of searching the actual buffer, the regexp engine could be made to search the buffer itself, and a copy of it with all text normalized, for some "good" definition of normalization. So looking for "iff" in "difficult" would really look for "iff" in both "difficult" and "difficult". Since normalization is a per-character operation, this does not require maintaining a second copy of the buffer: instead, one can just feed two streams of characters to the regexp engine: the un-normalized one, and the normalized one.

As a side note, it may also be possible to track at the buffer level whether the whole file is ascii; if it is, then case folding can be omitted, making any performance degradation stemming from character folding more acceptable. One can also use finer-grained control, especially if character folding happens at the C level in the regexp engine.

Cheers,
Clément.


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: Char-folding: how can we implement matching multiple characters as a single "thing"?

[Eli Zaretskii]

> From: Clément Pit--Claudel <clement.pit@gmail.com>
> Date: Mon, 30 Nov 2015 17:49:35 +0100
> 
> * Extend the C-level implementation of regular expressions to make character-folding a capability of the C engine, allowing for succinct regexps + a flag.
> * Add a new backslash to regular expressions for matching char-folded characters (custom character categories almost already allow for this, so the implementation would probably be similar).

The correct implementation for character folding is the same as for
case-folding: on the C level of the search.c routines.  This was
discussed back when this feature was in the design phase.  However,
the undertaking of coding this in search.c was too complex, so we
decided to go with the current implementation in Lisp and live with
its limitations for the time being.

Volunteers are welcome to work on the ultimate solution, which should
indeed include normalization of both the search string and the
buffer/string text that is searched.

Thanks.

Re: Char-folding: how can we implement matching multiple characters as a single "thing"?

[John Wiegley]

>>>>> Eli Zaretskii <eliz@gnu.org> writes:

> Volunteers are welcome to work on the ultimate solution, which should indeed
> include normalization of both the search string and the buffer/string text
> that is searched.

I imagine this would be done iteratively, with caching of what had been
normalized if we happen to back-track within a certain bound.

Any takers for working on the "ultimate solution"?

John

Re: Char-folding: how can we implement matching multiple characters as a single "thing"?

[Artur Malabarba]

All right. For now, I've gone with Paul's suggestion and just made the
algorithm dumber. It won't catch every single scenario, but that's
better than catching none.

I too agree that the ideal approach would be to implement this
entirely in C, but so far we lack the necessary human effort.

There's also a 3rd option. I posted some code here a while ago that
implemented char-folding by temporarily replacing the
(current-case-table) with a char-fold-table. This was fast, and much
nicer than the current regexps, but it had the limitation of only
being a character-to-character relation. So it couldn't do something
as basic as 'a' matching "ä" (because that's 1 char matching 2).

However, it's possible that we could combine the two solutions, using
this case-table for as much as possible and then using regexps for
anything else. This way the regexp pattern that replaces each input
character would likely be considerably smaller than 45 chars (I'd
guess between 3 and 15 depending on the character).
The number of branches would still scale badly with the input string
size. but the smaller multiplicative factor should give us more leeway
before scaling up to 10k chars.



2015-11-30 21:48 GMT+00:00 John Wiegley <jwiegley@gmail.com>:
>>>>>> Eli Zaretskii <eliz@gnu.org> writes:
>
>> Volunteers are welcome to work on the ultimate solution, which should indeed
>> include normalization of both the search string and the buffer/string text
>> that is searched.
>
> I imagine this would be done iteratively, with caching of what had been
> normalized if we happen to back-track within a certain bound.
>
> Any takers for working on the "ultimate solution"?
>
> John
>

Re: Char-folding: how can we implement matching multiple characters as a single "thing"?

[Eli Zaretskii]

> Date: Tue, 1 Dec 2015 14:18:30 +0000
> From: Artur Malabarba <bruce.connor.am@gmail.com>
> 
> There's also a 3rd option. I posted some code here a while ago that
> implemented char-folding by temporarily replacing the
> (current-case-table) with a char-fold-table. This was fast, and much
> nicer than the current regexps, but it had the limitation of only
> being a character-to-character relation. So it couldn't do something
> as basic as 'a' matching "ä" (because that's 1 char matching 2).
> 
> However, it's possible that we could combine the two solutions, using
> this case-table for as much as possible and then using regexps for
> anything else. This way the regexp pattern that replaces each input
> character would likely be considerably smaller than 45 chars (I'd
> guess between 3 and 15 depending on the character).
> The number of branches would still scale badly with the input string
> size. but the smaller multiplicative factor should give us more leeway
> before scaling up to 10k chars.

My gut feeling is that if we go to the C level, we should implement
this properly.  Coding another partial solution will almost certainly
bump into some subtle limitations.  In particular, any solution that
requires a literal search to use regexps under the hood will present
restrictions, because it will not play well with other regexp-based
features, like word search and C-M-s itself.

GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Drew Adams]

> I pushed this feature a couple of days ago, but I had to
> disable it now (the code is in `character-fold-to-regexp').

Where are the latest Lisp development sources mirrored now?

Looking in http://repo.or.cz/emacs.git/tree/refs/heads/master:/lisp
I don't think I'm seeing recent changes to character-fold.el,
for instance - the latest change to it seems to be from 11-12.

Re: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Steinar Bang]

>>>>> Drew Adams <drew.adams@oracle.com>:

>> I pushed this feature a couple of days ago, but I had to
>> disable it now (the code is in `character-fold-to-regexp').

> Where are the latest Lisp development sources mirrored now?

Why do you need a mirror?

What's wrong with http://savannah.gnu.org/git/?group=emacs ?

RE: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Drew Adams]

> > Where are the latest Lisp development sources mirrored now?
> 
> Why do you need a mirror?

I want to use it.  What does it matter whether I also
need it, or why?  Why do we have a mirror?  FWIW, I use
it (rarely) to obtain or inspect the odd source file.

> What's wrong with http://savannah.gnu.org/git/?group=emacs?

What's wrong with cauliflower? ;-)  Did someone say
there is something wrong with that URL?

It's not a simple http mirror of the source files, but
it might be a wonderful vegetable and a fine plant. ;-)
I have nothing against it.

In sum: not an answer to the question, but thanks anyway.

Re: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Artur Malabarba]

I didn't push to master, I pushed to emacs-25. Could that be the
reason why you didn't see it?

2015-12-01 16:31 GMT+00:00 Drew Adams <drew.adams@oracle.com>:
>> I pushed this feature a couple of days ago, but I had to
>> disable it now (the code is in `character-fold-to-regexp').
>
> Where are the latest Lisp development sources mirrored now?
>
> Looking in http://repo.or.cz/emacs.git/tree/refs/heads/master:/lisp
> I don't think I'm seeing recent changes to character-fold.el,
> for instance - the latest change to it seems to be from 11-12.

RE: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Drew Adams]

> I didn't push to master, I pushed to emacs-25. Could that be the
> reason why you didn't see it?

OK, I found the mirror at:
http://repo.or.cz/emacs.git/tree/refs/heads/emacs-25:/lisp,
and I've updated my bookmark.  I guess I'll need to update
it each time you branch a pre-pre-release development, from
now on?

(Why doesn't master hold the latest developments, just as
(IIUC) it has always done in the past?)

Re: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Karl Fogel]

Drew Adams <drew.adams@oracle.com> writes:
>(Why doesn't master hold the latest developments, just as
>(IIUC) it has always done in the past?)

During release stabilization, at least in recent releases that I can remember, the maintainers have asked that changes go to the release branch first and then get (automagically or semi-automagically) ported to 'master' later.  So that's what we've been doing for a while.  I think it's partly just to ensure that what's about to be released gets live-tested as much as possible by the developers.

I don't know when this release branch policy was first instituted, and am not suggesting that it's better or worse than a master-first policy.  But it's what we've been doing.  IIRC John W. speculated that we might do differently for the next release, but said he didn't want to change it for this release.  I don't remember which email I saw that in, though.

Best regards,
-Karl

Re: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Artur Malabarba]

[-- Attachment #1: Type: text/plain, Size: 570 bytes --]

On 1 Dec 2015 6:29 pm, "Karl Fogel" <kfogel@red-bean.com> wrote:
>
> Drew Adams <drew.adams@oracle.com> writes:
> >(Why doesn't master hold the latest developments, just as
> >(IIUC) it has always done in the past?)
>
> During release stabilization, at least in recent releases that I can
remember, the maintainers have asked that changes go to the release branch
first and then get ported to 'master' later.

Except for new features, that is. The emacs-25 branch is for refining what
will get release. The master branch is still the place where we add brand
new stuff.

[-- Attachment #2: Type: text/html, Size: 787 bytes --]

RE: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Drew Adams]

> > > (Why doesn't master hold the latest developments, just as
> > > (IIUC) it has always done in the past?)
> >
> > During release stabilization, at least in recent releases that
> > I can remember, the maintainers have asked that changes go to
> > the release branch first and then get ported to 'master' later.  
> 
> Except for new features, that is. The emacs-25 branch is for
> refining what will get release. The master branch is still
> the place where we add brand new stuff.

This is a new feature, is it not?  Are we supposed to look to
`master' only for an initial implementation of a new feature,
and then look to an `emacs-N' branch for its post-branching
improvement?

RE: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Artur Malabarba]

[-- Attachment #1: Type: text/plain, Size: 1569 bytes --]

On 1 Dec 2015 9:18 pm, "Drew Adams" <drew.adams@oracle.com> wrote:
>
> > > > (Why doesn't master hold the latest developments, just as
> > > > (IIUC) it has always done in the past?)
> > >
> > > During release stabilization, at least in recent releases that
> > > I can remember, the maintainers have asked that changes go to
> > > the release branch first and then get ported to 'master' later.
> >
> > Except for new features, that is. The emacs-25 branch is for
> > refining what will get release. The master branch is still
> > the place where we add brand new stuff.
>
> This is a new feature, is it not?  Are we supposed to look to
> `master' only for an initial implementation of a new feature,
> and then look to an `emacs-N' branch for its post-branching
> improvement?

A few weeks ago, Emacs 25 entered feature freeze. This means a new branch
called emacs-25 was created (at the time, it contained everything that was
on master). Since then, any new features should go to the master branch,
while bug fixes and refinements should go to the emacs-25 branch (these are
later merged onto master too).

This way we can have several months to polish off the next release (on the
emacs-25 branch) without forcing everybody to stop adding shiny new things
(the shiny new things are just added to master instead).

The character-folding feature was added to master before the feature
freeze. So it is now part of the emacs-25 branch. Any further refinements
to this feature will therefore go on the emacs-25 branch (to make sure the
release is as good as possible).

[-- Attachment #2: Type: text/html, Size: 1907 bytes --]

RE: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Drew Adams]

> any new features should go to the master branch, while bug fixes
> and refinements should go to the emacs-25 branch (these are later
> merged onto master too).

It's the "later" that means that master is not necessarily
up-to-date.  It means that looking to master does not give
you the latest developments - until sometime "later".

I wouldn't think that the changes you made recently to
support multiple-char folding on `emacs-25' (and that you
later disabled) are just "bug fixes and refinements".
They change the behavior/design, IIUC.  Seems like it
might have been good to sync `master' then (at least as
far as that file is concerned).

Anyway, I guess the answer, to how to get the latest
changes, is to check a file in both `master' and
`emacs-25', and pick whichever one is more recent.

RE: GIT mirror of Lisp dev sources [was: Char-folding: how can we implement matching...]

[Artur Malabarba]

[-- Attachment #1: Type: text/plain, Size: 782 bytes --]

On 2 Dec 2015 12:14 am, "Drew Adams" <drew.adams@oracle.com> wrote:
>
> > any new features should go to the master branch, while bug fixes
> > and refinements should go to the emacs-25 branch (these are later
> > merged onto master too).
>
> It's the "later" that means that master is not necessarily
> up-to-date.  It means that looking to master does not give
> you the latest developments - until sometime "later".

Yes.

The sync to master would normally happen somewhat frequently. Currently
it's delayed until we solve a technical issue with the new changelog
system.

That said, anyone who follows the development version because they want to
help find bugs and issues should probably switch to the emacs-25 branch
until release. As that's where we need the most polish now.

[-- Attachment #2: Type: text/html, Size: 1019 bytes --]