Closed angstyloop closed 8 months ago
This is what the empty TextView looks like right now.
Here is a Gist with an example that shows how VIPS will be used to access the metadata as though we typed vipsheader -a
at the command line.
https://gist.github.com/angstyloop/e0faf930b4978a8fcd24e5c9255f884e
Sure, PR away. You'll probably need a treecolumn to the right rather than a textview.
Sure, PR away. You'll probably need a treecolumn to the right rather than a textview.
Tabular is definitely better! Looks like ColumnView is what GTK4 suggests over TreeViewColumn. I doubt you have a strong opposition to using one over the other, but if so I'm all ears.
I'll probably start with just name and value. The EXIF tags have multiple components sometimes, so those could maybe be handled separately. Tabular name and value is maybe a good starting point? I'm open to whatever.
With metadata. Still a work in progress.
Ah columnview, use that, sure. I just got the names mixed up.
I'd think you'd need some kind of search or filter box (metadata can get very large) plus an X button to close the popover again. Beyond that, it's all up to you!
What happens to the popover in fullscreen mode, out of curiosity?
Ah columnview, use that, sure. I just got the names mixed up.
I'd think you'd need some kind of search or filter box (metadata can get very large) plus an X button to close the popover again. Beyond that, it's all up to you!
Since your vast knowledge of GTK over multiple versions is impressive, I'll let this one slide! Haha
There needs to be some way to limit the amount of data shown to the user - I think a search is great.
Also, it would be a way to limit the amount of metadata loaded into memory. As far as I can tell, there is not a limit to the amount of metadata for image formats other than JPEG. I was wondering if loading the full metadata into memory might actually be enough to slow vipsdisp down noticeably when the app starts, or when the popover is opened.
libvips always loads all the metadata, so I don't think there's a useful saving trying to limit it.
(it uses reference counts for metadata items, so they are each only loaded once and it's just pointer copies after that ... no need to worry about efficiency there)
What happens to the popover in fullscreen mode, out of curiosity?
Total weirdness.
If you have the Metadata setting on, so that the popover is open, and then you focus the image window and hit F11, you will go into fullscreen mode. The popover stays visible since its autohide property is false, and it is inconveniently shifted to near the center of the screen, where the image is located, covering it.
At that point, if you hit F11 again, you will exit fullscreen mode, but the popover will disappear completely
If you hit F11 again, you will go into fullscreen mode, still with no popover.
But if you hit F11 again, you will exit fullscreen mode, and the popover is back! The cycle continues if you keep pressing F11.
libvips always loads all the metadata, so I don't think there's a useful saving trying to limit it.
(it uses reference counts for metadata items, so they are each only loaded once and it's just pointer copies after that ... no need to worry about efficiency there)
Wow, that's cool - noted for future reference!
That means I only have to worry about limiting what is shown to the user, which a search seems good for like you said.
With GtkColumnView now
I wonder if instead of a popover, the image window should just get bigger to accomodate a metadata menu next to the image. That would also look good in full screen mode. ( Should I have done the SaveOptions menu like that? ... )
Alternatively, it can cover up part of the image, and remain inside the bounds of the image window, but it seems wrong to obscure the image just to see the metadata - not a necessary tradeoff.
If the popover seems fine for now though, I'll jump into search next
Implementing search this week! I will ideally be leveraging GtkSearchEntry widget, which is already debounced out of the box. Pretty cool that GTK provides that. https://docs.gtk.org/gtk4/class.SearchEntry.html
I faster-than-linear search is possible - with a little added memory complexity of course. It might be worthwhile to compare later, but I'll start with the simplest implementation.
Yeah I didn't try to be optimal or anything, but so far I've been able to implement a basic proof-of-concept search UI (outside of VIPSDISP).
I was able to take it one step further and markup the matching substrings. I chose boldface as an example, but I can apply any GTK4-supported CSS to the matching substrings. I can also just forego marking up the substrings if it's undesired.
Sure, bold looks nice!
Works for me then
Since I was already using GRegex for matching and replacing strings, a few small adjustments to the UI allowed for a regex search option. Here is an example of what that functionality would look like.
While a neat demo, this may be overkill for the metadata tag name search.
Although, some of those EXIF tag names can be pretty perilous to type haha
Maybe a fuzzy match would be useful? That's much harder to implement though.
challenge accepted!
I'd like to try something with the Bitap algorithm
Here's what I learned about it:
Bitap is not exclusively for approximate string matching, but that is a popular use case for it
Apparently, that's what agrep
uses
It's considered to be fast for the size of typical pattern strings we are dealing with
It's an on-line algorithm, so it doesn't do indexing, which to me is a plus
There are existing implementations in C I can refer to
The Bitap algorithm has a string size limit on the target string ( the "haystack" ) of either 31 characters or 63 characters. The implementation with 31 characters is at least twice as fast, and probably more because the bit operations are on smaller integer types, but those claims are not backed up by tests I've done myself. I suspect it will be plenty fast.
As for the character limit on the tag name... well, I actually think that is fine... @jcupitt ?
The EXIF tag names and TIFF tag names exceed 31 characters, let alone 63. Is this on purpose - can I trust it? I'll probably have to track down some really technical IETF document to find out.
Shamelessly stole an example implementation from the Wikipedia article on the Bitapp algorithm ( which could really use a visual aid IMO ... ) . The size limit can be doubled by changing unsigned long to unsigned long long and changing 31 to 63.
And yes, I know what each line of code does! Lol
One cool part about Bitapp is it can differentiate an exact match from a fuzzy match. More than that, it keeps track of how many errors each match has. Finally, even though the example only finds the first match, it can easily be modified to find every match, and track the other details I mentioned.
/*
COMPILE
gcc -o bitapp bitapp.c
RUN
./bitap
*/
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdio.h>
/* Find the first match of @pattern in @string with at most @k substitution
* errors.
*
* @text - The string we are searching to find @pattern.
*
* @pattern - The string we are trying to find in @text.
*
* @k - The maximum number of allowed errors. If k is zero, then the match is
* exact.
*
* @returns A pointer to the character in @text where the first match found
* starts.
*/
const char *bitap_fuzzy_bitwise_search( const char *text,
const char *pattern, int k)
{
const char *result = NULL;
int m = strlen(pattern);
unsigned long *R;
unsigned long pattern_mask[CHAR_MAX+1];
int i, d;
if (pattern[0] == '\0') return text;
if (m > 31) return "The pattern is too long!";
/* Initialize the bit array R */
R = malloc((k+1) * sizeof *R);
for (i=0; i <= k; ++i)
R[i] = ~1;
/* Initialize the pattern bitmasks */
for (i=0; i <= CHAR_MAX; ++i)
pattern_mask[i] = ~0;
for (i=0; i < m; ++i)
pattern_mask[pattern[i]] &= ~(1UL << i);
for (i=0; text[i] != '\0'; ++i) {
/* Update the bit arrays */
unsigned long old_Rd1 = R[0];
R[0] |= pattern_mask[text[i]];
R[0] <<= 1;
for (d=1; d <= k; ++d) {
unsigned long tmp = R[d];
/* Substitution is all we care about */
R[d] = (old_Rd1 & (R[d] | pattern_mask[text[i]])) << 1;
old_Rd1 = tmp;
}
if (0 == (R[k] & (1UL << m))) {
result = (text+i - m) + 1;
break;
}
}
free(R);
return result;
}
int main() {
const char *text = "hhhhhhhhhhhhereeeeeeeeeeeeeeeee";
const char *pattern = "heee";
int k = 1;
const char *a =
bitap_fuzzy_bitwise_search( text, pattern, k );
puts( a );
}
You could do two searches: do a search for exact matches first and display those, then do a second search for bitapp matches on the first 32 characters and show those at the end. You'd probably want exact matches first anyway.
I doubt if speed will be an issue heh. I think I'd do a 64 character match.
I had a quick look and the longest name I found was exif-ifd2-ComponentsConfiguration
at 33 characters. I expect there are longer ones.
Oh drat, you have to count the length of the "exif-blah" prefix ...
It's worth mentioning Bitap will find exact matches at the same time as the fuzzy ones, and Bitap with k=0 is exact match. I was just going to order them by increasing number of errors ( usually denoted "k" ). So whenever the tag name has length smaller than 63, I can just use Bitap, and it sorts exactly how you want.
If the length is longer than 63, it would then be necessary to do it exactly like you said. Will it be that long? I'm comfortable having a backup just in case ( unless you think a 63 character tag name simply doesn't exist ).
In theory they can be any length, so I think it would be safest to have a backup.
That's what I'll do then!
I found a more appropriate implementation that uses good ol' linked lists instead of bitwise operations, and imposes no limit on pattern size.
It is the same algorithm though - just counting mismatches in strings of a fixed-size alphabet.
The example code statically allocates a pool of match structs initialized with placeholder values. I'll modify it to dynamically allocate the structs as needed instead.
I don't think the UI is going to lag or anything - I'm eager to find out!
/* match_with_mismatches.c
*
* Search for a substring of @text matching @pattern, with @k or fewer
* mismatches (substitutions).
*
* COMPILE
*
* gcc -o match_with_mismatches match_with_mismatches.c
*
* RUN
*
* ./match_with_mismatches
*
* REFS
*
* The search and preprocess functions were taken from the example code from
* "Fast and Practical Approximate String Matching" by Baeza-Yates.
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define SIZE 256 /* size of alpha index and count array */
#define MOD256 0xff /* for the mod operation */
typedef struct idxnode { /* structure for index of alphabet */
int offset; /* distance of char from start of pattern */
struct idxnode *next; /* pointer to next idxnode if it exists */
} anode;
anode alpha[SIZE]; /* offset for each alphabetic character */
int count[SIZE]; /* count of the characters that don't match */
/* string searching with mismatches */
int search(
char *t, /* text */
int n, /* number of characters in text */
int m /* number of characters in pattern */,
int k, /* the number of mismatches */
anode alpha[], /* index of alphabet */
int count[] ) /* circular buffer of count of mismatched characters */
{
int i, off1;
anode *aptr;
for ( i=0; i<n; i++ ) {
if ( (off1 = (aptr = &alpha[*t++])->offset) >= 0) {
count[(i + off1) & MOD256]--;
for ( aptr = aptr->next; aptr != NULL; aptr = aptr->next )
count[(i + aptr->offset) & MOD256]--;
}
if ( count[i & MOD256] <= k )
printf("Match in position %d with %d mismatches.\n",
i - m + 1, count[i & MOD256] );
count[i & MOD256] = m;
}
}
/* preprocessing routine */
int preprocess(
char *p, /* pointer to pattern */
int m, /* number of characters in pattern */
anode alpha[], /* alphabetical index giving offsets */
int count[] ) /* circular buffer for counts of mismatches */
{
int i, j;
anode *aptr;
for ( i = 0; i < SIZE; i++ ) {
alpha[i].offset = -1;
alpha[i].next = NULL;
count[i] = m;
}
for ( i = 0, j = 128; i < m; i++, p++ ) {
count[i] = SIZE;
if ( alpha[*p].offset == -1 )
alpha[*p].offset = m - i - 1;
else {
aptr = alpha[*p].next;
alpha[*p].next = &alpha[j++];
alpha[*p].next->offset = m - i - 1;
alpha[*p].next->next = aptr;
}
}
count[m - 1] - m;
}
int main()
{
/* Modify @pattern, @text, and @number_of_mismatches to play with the
* code.
*/
char *pattern = "abc", *text = "xxxadcxxx";
int number_of_mismatches = strlen(pattern);
preprocess( pattern, strlen( pattern ), alpha, count );
search( text, strlen( text ), strlen( pattern ), number_of_mismatches,
alpha, count );
return 0;
}
It will still work like we talked about, listing the exact matches first, followed by the matches with one wrong character, then two, and so on - I just don't need to treat two separate cases based on pattern length.
I've been quiet here, so I just wanted to update.
I'm working on a personal project for the Linux 2023 Game Jam hosted by itchi.io, and before that I was playing a lot of video games in my spare time. So I haven't been working on this for a bit. BUT the jam is over in a few days. I'll be back to it pretty shortly after that.
I used VIPS to automate some sprite creation. The fill operation was really convenient, as it let me create a "color by coordinates" template. The if-else was what I was using at first - in that case the template and replacement were based on pixel value.
VIPS is used by scientists. But as it turns out, it's also really nice for making sprites for indie games! haha
Yup, TOTK is eating any free time I have heh
TOTK is great - it's fun to just explore and build stuff! I could spend hours just doing that lol.
Game jam is finally over! Here's that if you're interested:
https://angstyloop.itch.io/ji/devlog/541996/submitted-ji-to-the-linux-2023-game-jam
I'll be back in VIPSDISP land soon : )
Oh, nice!
I made a few pico8 games, it's a little similar I guess, eg.:
https://www.lexaloffle.com/bbs/?tid=28243
I have a playdate I've been meaning to try stuff on, but no time yet :(
Amazing
Fuzzy match code uses GLib now, and is almost ready to drop into VIPSDISP. I will make a small demo GTK app first.
https://gist.github.com/angstyloop/a0efcb110b27ebc91fed5ae78e7ad009
Here is a demo GTK4 app that uses the new fuzzy match (without marked up match text)
Needs improvements:
A maximum number of allowed mismatches of 3 was selected. We will have to decide on a limit for the usage in VIPSDISP. I don't think that allowing mismatches up to the length of the pattern string is very helpful. I think strings with only a few mismatches are more appropriate for munging. If there are too many allowed mismatches, as the user I start to wonder "why am I being shown this"?
Results are sorted by number of mismatches k, but the matches with k=0 should be set apart even more somehow. A clickable "view more" button or label that always shows at the end of the list seems like a good approach to me. If we only show it when there are no exact matches, we lose a little bit of the functionality. Discreetly giving the option to always toggle fuzzy matches on/off seems like a good way to go.
Match highlighting, at least on exact matches, is still a nice touch, and still needs to be redone. I don't think we want to highlight inexact matches though. It would look weird when the user types in "bbb" and sees "png" highlighted in the tag name. That's not helpful to see, unlike a highlighted exact match.
Gists
Oh that looks very cool! Nice job.
I wonder if this would be generally useful?
I don't think glib has a fuzzy match function. You could consider making a PR on glib with this code. They'd want to to handle utf-8, of course, which might be annoying to implement.
Ahh, I just found your post on gnome where you proposed exactly this. Nevermind.
Thank you! Interacting with more GNOME people was cool. Maybe someone will find my one of my examples and run with it.
Progress!
Exact matches are bolded. Fuzzy matches are only shown if there are no exact matches, but I removed the hard limit on the number of mismatches. Instead, the largest possible number of mismatches is always the length of the metadata field being examined.
This may show a lot of results for small pattern strings with no exact match, but that is fine, because the correct one is usually at the top. I think this is because the metadata field names I have tested with are well separated in terms of hamming distance.
In the demo, I show some examples of inputs the user might accidentally type.
Originally I used GtkPopover as the container for the metadata widget, just to get started, but this this not really the intended use of GtkPopover.
Instead I could do something like this:
Note there are some weird, sporadic issues when the GTK4 PopoverMenu is active after a window resize, but I think that's a GTK4 bug.
Same thing, larger window
Ah nice. Yes, that's probably simpler.
I think I'll do "edit metadata" as part of this PR, too, instead of opening a new one, since they will be so related. I think that's going to take a lot of changes, so I'm going to clean up this code first and then probably take a little break.
In retrospect, Levenshtein distance would be a better algorithm to use for fuzzy match, since it handles insertions/deletions/substitution errors and has adjustable penalties for these errors.
The Baeza-Yates-Perleberg one is still cool though. I'll make the switch after the metadata editing feature is done.
Since the metadata are just GValues on a VipsImage, this feature will be similar to the save options menu, except
I will try to unpack the "image-description" tag on TIFF images, and let users edit the individual key/value pairs.
At first I will try to just reuse some code from the save options branch to show UI input widgets for the basic types. Then I can build UI for the more complicated types as needed, which will also feed back into the save options work.
"image-description" is just a text string, though it can have XML in there.
IPCT is always XML, maybe that would be a good one to support?
https://en.wikipedia.org/wiki/IPTC_Information_Interchange_Model
Though an XML editor is a large job!
Agreed - it would take a while for me to write an XMP editor in C GTK - that probably deserves its own PR. It might be cool to do that later. I see that libxml is part of the VIPS dependencies already, which is nice.
Is there a "too early" for making a draft PR?
This is a draft, far from being complete. So far, I have added a "metadata" GSetting and menu item that toggles the visibility of an empty TextView inside a Popover to the right of the ImageWindow.