[xdg-desktop-portal-gnome/gbsneto/screencast-session-restore: 1/2] Implement screencast stream restoration

[Georges Basile Stavracas Neto <gbsneto src gnome org>]

commit e37c04528847001a9944545704a1c6f81d12bbd4
Author: Georges Basile Stavracas Neto <georges stavracas gmail com>
Date:   Tue Sep 28 21:04:28 2021 -0300

    Implement screencast stream restoration
    
    Handle receiving 'restore_data' and 'persist_mode'.
    
    For monitors, use the match string introduced by the previous
    commit to identify individual monitors. For windows, do a strict
    check on the app id, and a best-match approach to window titles.
    
    Virtual monitors cannot be restored.

 src/screencast.c        | 336 ++++++++++++++++++++++++++++++++++++++++++++++--
 src/screencast.h        |   7 +
 src/screencastdialog.c  |  14 +-
 src/screencastdialog.h  |   5 +-
 src/screencastwidget.c  |  23 ++++
 src/screencastwidget.h  |   6 +
 src/screencastwidget.ui |   8 ++
 src/utils.c             |  77 +++++++++++
 src/utils.h             |   3 +
 9 files changed, 465 insertions(+), 14 deletions(-)
---
diff --git a/src/screencast.c b/src/screencast.c
index 2713d26..8b16767 100644
--- a/src/screencast.c
+++ b/src/screencast.c
@@ -33,8 +33,15 @@
 #include "externalwindow.h"
 #include "request.h"
 #include "session.h"
+#include "shellintrospect.h"
 #include "utils.h"
 
+#define RESTORE_FORMAT_VERSION 1
+#define RESTORE_VARIANT_TYPE "(suxxa(uuv))"
+#define MONITOR_TYPE "s"
+#define WINDOW_TYPE "(ss)"
+#define VIRTUAL_TYPE "b"
+
 typedef struct _ScreenCastDialogHandle ScreenCastDialogHandle;
 
 typedef struct _ScreenCastSession
@@ -49,6 +56,12 @@ typedef struct _ScreenCastSession
 
   ScreenCastSelection select;
 
+  ScreenCastPersistMode persist_mode;
+  struct {
+    GVariant *data;
+    int64_t creation_time;
+  } restored;
+
   GDBusMethodInvocation *start_invocation;
   ScreenCastDialogHandle *dialog_handle;
 } ScreenCastSession;
@@ -99,6 +112,77 @@ screen_cast_dialog_handle_close (ScreenCastDialogHandle *dialog_handle)
   screen_cast_dialog_handle_free (dialog_handle);
 }
 
+static GVariant *
+serialize_streams_as_restore_data (GPtrArray *streams,
+                                   int64_t    creation_time)
+{
+  GVariantBuilder restore_data_builder;
+  int64_t last_used_time;
+  guint i;
+
+  if (!streams || streams->len == 0)
+    return NULL;
+
+  last_used_time = g_get_real_time ();
+
+  g_variant_builder_init (&restore_data_builder, G_VARIANT_TYPE (RESTORE_VARIANT_TYPE));
+  g_variant_builder_add (&restore_data_builder, "s", "GNOME");
+  g_variant_builder_add (&restore_data_builder, "u", RESTORE_FORMAT_VERSION);
+  g_variant_builder_add (&restore_data_builder, "x", creation_time);
+  g_variant_builder_add (&restore_data_builder, "x", last_used_time);
+
+  g_variant_builder_open (&restore_data_builder, G_VARIANT_TYPE ("a(uuv)"));
+  for (i = 0; i < streams->len; i++)
+    {
+      ScreenCastStreamInfo *info = g_ptr_array_index (streams, i);
+      GVariant *stream_variant;
+      Monitor *monitor;
+      Window *window;
+
+      switch (info->type)
+        {
+        case SCREEN_CAST_SOURCE_TYPE_MONITOR:
+          monitor = info->data.monitor;
+          stream_variant = g_variant_new (MONITOR_TYPE,
+                                          monitor_get_match_string (monitor));
+          break;
+
+        case SCREEN_CAST_SOURCE_TYPE_WINDOW:
+          window = info->data.window;
+          stream_variant = g_variant_new (WINDOW_TYPE,
+                                          window_get_app_id (window),
+                                          window_get_title (window));
+          break;
+
+        case SCREEN_CAST_SOURCE_TYPE_VIRTUAL:
+          /*
+           * D-Bus doesn't accept maybe types, so just pass bogus boolean. It
+           * doesn't really matter since we'll never actually read this value.
+           */
+          stream_variant = g_variant_new (VIRTUAL_TYPE, TRUE);
+          break;
+        }
+
+      g_variant_builder_add (&restore_data_builder,
+                             "(uuv)",
+                             i,
+                             info->type,
+                             stream_variant);
+    }
+  g_variant_builder_close (&restore_data_builder);
+
+  return g_variant_builder_end (&restore_data_builder);
+}
+
+static int64_t
+get_screencast_session_creation_time (ScreenCastSession *screen_cast_session)
+{
+  if (screen_cast_session->restored.creation_time != -1)
+    return screen_cast_session->restored.creation_time;
+
+  return g_get_real_time ();
+}
+
 static void
 cancel_start_session (ScreenCastSession *screen_cast_session,
                       int response)
@@ -142,6 +226,15 @@ on_gnome_screen_cast_session_ready (GnomeScreenCastSession *gnome_screen_cast_se
                          "streams",
                          g_variant_builder_end (&streams_builder));
 
+  if (screen_cast_session->persist_mode != SCREEN_CAST_PERSIST_MODE_NONE &&
+      screen_cast_session->restored.data)
+    {
+      g_variant_builder_add (&results_builder, "{sv}", "persist_mode",
+                             g_variant_new_uint32 (screen_cast_session->persist_mode));
+      g_variant_builder_add (&results_builder, "{sv}", "restore_data",
+                             g_variant_new_variant (screen_cast_session->restored.data));
+    }
+
   xdp_impl_screen_cast_complete_start (XDP_IMPL_SCREEN_CAST (impl),
                                        screen_cast_session->start_invocation, 0,
                                        g_variant_builder_end (&results_builder));
@@ -193,6 +286,7 @@ start_session (ScreenCastSession  *screen_cast_session,
 static void
 on_screen_cast_dialog_done_cb (GtkWidget              *widget,
                                int                     dialog_response,
+                               ScreenCastPersistMode   persist_mode,
                                GPtrArray              *streams,
                                ScreenCastDialogHandle *dialog_handle)
 {
@@ -218,8 +312,26 @@ on_screen_cast_dialog_done_cb (GtkWidget              *widget,
 
   if (response == 0)
     {
+      ScreenCastSession *screen_cast_session = dialog_handle->session;
       g_autoptr(GError) error = NULL;
 
+      if (persist_mode != SCREEN_CAST_PERSIST_MODE_NONE)
+        {
+          GVariant *restore_data;
+          int64_t creation_time;
+
+          creation_time = get_screencast_session_creation_time (screen_cast_session);
+          restore_data = serialize_streams_as_restore_data (streams, creation_time);
+
+          g_clear_pointer (&screen_cast_session->restored.data, g_variant_unref);
+          if (restore_data)
+            {
+              screen_cast_session->restored.data = g_variant_ref_sink (restore_data);
+              screen_cast_session->persist_mode = MIN (screen_cast_session->persist_mode,
+                                                       persist_mode);
+            }
+        }
+
       if (!start_session (dialog_handle->session, streams, &error))
         {
           g_warning ("Failed to start session: %s", error->message);
@@ -269,7 +381,8 @@ create_screen_cast_dialog (ScreenCastSession     *session,
   g_object_ref_sink (fake_parent);
 
   dialog = GTK_WIDGET (screen_cast_dialog_new (request->app_id,
-                                               &session->select));
+                                               &session->select,
+                                               session->persist_mode));
   gtk_window_set_transient_for (GTK_WINDOW (dialog), GTK_WINDOW (fake_parent));
   gtk_window_set_modal (GTK_WINDOW (dialog), TRUE);
 
@@ -295,6 +408,184 @@ create_screen_cast_dialog (ScreenCastSession     *session,
   return dialog_handle;
 }
 
+static Monitor *
+find_monitor_by_string (const char *monitor_string)
+{
+  DisplayStateTracker *display_state_tracker = display_state_tracker_get ();
+  GList *l;
+
+  for (l = display_state_tracker_get_logical_monitors (display_state_tracker);
+       l;
+       l = l->next)
+    {
+      LogicalMonitor *logical_monitor = l->data;
+      GList *monitors;
+
+      for (monitors = logical_monitor_get_monitors (logical_monitor);
+           monitors;
+           monitors = monitors->next)
+        {
+          Monitor *monitor = monitors->data;
+
+          if (g_strcmp0 (monitor_get_match_string (monitor), monitor_string) == 0)
+            return monitor;
+        }
+    }
+
+  return NULL;
+}
+
+static Window *
+find_best_window_by_app_id_and_title (const char *app_id,
+                                      const char *title)
+{
+  ShellIntrospect *shell_introspect = shell_introspect_get ();
+  Window *best_match;
+  glong best_match_distance;
+  GList *l;
+
+  best_match = NULL;
+  best_match_distance = G_MAXLONG;
+
+  for (l = shell_introspect_get_windows (shell_introspect); l; l = l->next)
+    {
+      Window *window = l->data;
+      glong distance;
+
+      if (g_strcmp0 (window_get_app_id (window), app_id) != 0)
+        continue;
+
+      distance = str_distance (window_get_title (window), title);
+
+      if (distance == 0)
+        return window;
+
+      if (distance < best_match_distance)
+        {
+          best_match = window;
+          best_match_distance = distance;
+        }
+    }
+
+  return best_match;
+}
+
+static gboolean
+restore_stream_from_data (ScreenCastSession *screen_cast_session)
+
+{
+  ScreenCastStreamInfo *info;
+  g_autofree gchar *provider = NULL;
+  g_autoptr(GVariantIter) array_iter = NULL;
+  g_autoptr(GPtrArray) streams = NULL;
+  g_autoptr(GError) error = NULL;
+  ScreenCastSourceType source_type;
+  GVariant *data;
+  uint32_t version;
+  uint32_t id;
+  int64_t creation_time;
+  int64_t last_used_time;
+
+  if (!screen_cast_session->restored.data)
+    return FALSE;
+
+  streams = g_ptr_array_new_with_free_func (g_free);
+
+  g_variant_get (screen_cast_session->restored.data,
+                 "(suxxa(uuv))",
+                 &provider,
+                 &version,
+                 &creation_time,
+                 &last_used_time,
+                 &array_iter);
+
+  if (g_strcmp0 (provider, "GNOME") != 0)
+    return FALSE;
+
+  if (version != RESTORE_FORMAT_VERSION)
+    return FALSE;
+
+  while (g_variant_iter_next (array_iter, "(uuv)", &id, &source_type, &data))
+    {
+      switch (source_type)
+        {
+        case SCREEN_CAST_SOURCE_TYPE_MONITOR:
+          {
+            if (!(screen_cast_session->select.source_types & SCREEN_CAST_SOURCE_TYPE_MONITOR) ||
+                !g_variant_check_format_string (data, MONITOR_TYPE, FALSE))
+              goto fail;
+
+            const char *match_string = g_variant_get_string (data, NULL);
+            Monitor *monitor = find_monitor_by_string (match_string);
+
+            if (!monitor)
+              goto fail;
+
+            info = g_new0 (ScreenCastStreamInfo, 1);
+            info->type = SCREEN_CAST_SOURCE_TYPE_MONITOR;
+            info->data.monitor = monitor;
+            g_ptr_array_add (streams, info);
+          }
+          break;
+
+        case SCREEN_CAST_SOURCE_TYPE_WINDOW:
+          {
+            if (!(screen_cast_session->select.source_types & SCREEN_CAST_SOURCE_TYPE_WINDOW) ||
+                !g_variant_check_format_string (data, WINDOW_TYPE, FALSE))
+              goto fail;
+
+            const char *app_id = NULL;
+            const char *title = NULL;
+            Window *window;
+
+            g_variant_get (data, "(&s&s)", &app_id, &title);
+
+            window = find_best_window_by_app_id_and_title (app_id, title);
+
+            if (!window)
+              goto fail;
+
+            info = g_new0 (ScreenCastStreamInfo, 1);
+            info->type = SCREEN_CAST_SOURCE_TYPE_WINDOW;
+            info->data.window = window;
+            g_ptr_array_add (streams, info);
+          }
+          break;
+
+        case SCREEN_CAST_SOURCE_TYPE_VIRTUAL:
+          {
+            if (!(screen_cast_session->select.source_types & SCREEN_CAST_SOURCE_TYPE_VIRTUAL) ||
+                !g_variant_check_format_string (data, VIRTUAL_TYPE, FALSE))
+              goto fail;
+
+            info = g_new0 (ScreenCastStreamInfo, 1);
+            info->type = SCREEN_CAST_SOURCE_TYPE_VIRTUAL;
+            info->id = id;
+            g_ptr_array_add (streams, info);
+          }
+          break;
+
+        default:
+          goto fail;
+        }
+    }
+
+  screen_cast_session->restored.creation_time = creation_time;
+
+  start_session (screen_cast_session, streams, &error);
+
+  if (error)
+    {
+      g_warning ("Error restoring stream from session: %s", error->message);
+      return FALSE;
+    }
+
+  return TRUE;
+
+fail:
+  return FALSE;
+}
+
 static gboolean
 handle_start (XdpImplScreenCast     *object,
               GDBusMethodInvocation *invocation,
@@ -307,7 +598,6 @@ handle_start (XdpImplScreenCast     *object,
   const char *sender;
   g_autoptr(Request) request = NULL;
   ScreenCastSession *screen_cast_session;
-  ScreenCastDialogHandle *dialog_handle;
   GVariantBuilder results_builder;
 
   sender = g_dbus_method_invocation_get_sender (invocation);
@@ -329,14 +619,19 @@ handle_start (XdpImplScreenCast     *object,
       goto err;
     }
 
-  dialog_handle = create_screen_cast_dialog (screen_cast_session,
-                                             invocation,
-                                             request,
-                                             arg_parent_window);
+  screen_cast_session->start_invocation = invocation;
 
+  if (!restore_stream_from_data (screen_cast_session))
+    {
+      ScreenCastDialogHandle *dialog_handle;
 
-  screen_cast_session->start_invocation = invocation;
-  screen_cast_session->dialog_handle = dialog_handle;
+      dialog_handle = create_screen_cast_dialog (screen_cast_session,
+                                                 invocation,
+                                                 request,
+                                                 arg_parent_window);
+
+      screen_cast_session->dialog_handle = dialog_handle;
+    }
 
   return TRUE;
 
@@ -356,6 +651,8 @@ handle_select_sources (XdpImplScreenCast     *object,
                        const char            *arg_app_id,
                        GVariant              *arg_options)
 {
+  g_autoptr(GVariant) restore_data = NULL;
+  ScreenCastSession *screen_cast_session;
   Session *session;
   int response;
   uint32_t types;
@@ -427,6 +724,18 @@ handle_select_sources (XdpImplScreenCast     *object,
       response = 2;
     }
 
+  screen_cast_session = (ScreenCastSession *)session;
+  g_variant_lookup (arg_options, "persist_mode", "u", &screen_cast_session->persist_mode);
+  g_variant_lookup (arg_options, "restore_data", "v", &restore_data);
+
+  if (restore_data)
+    {
+      if (g_variant_check_format_string (restore_data, RESTORE_VARIANT_TYPE, FALSE))
+        screen_cast_session->restored.data = g_variant_ref (restore_data);
+      else
+        g_warning ("Cannot parse restore data, ignoring");
+    }
+
 out:
   g_variant_builder_init (&results_builder, G_VARIANT_TYPE_VARDICT);
   results = g_variant_builder_end (&results_builder);
@@ -567,6 +876,7 @@ screen_cast_session_finalize (GObject *object)
 {
   ScreenCastSession *screen_cast_session = (ScreenCastSession *)object;
 
+  g_clear_pointer (&screen_cast_session->restored.data, g_variant_unref);
   g_clear_object (&screen_cast_session->gnome_screen_cast_session);
 
   G_OBJECT_CLASS (screen_cast_session_parent_class)->finalize (object);
@@ -575,6 +885,8 @@ screen_cast_session_finalize (GObject *object)
 static void
 screen_cast_session_init (ScreenCastSession *screen_cast_session)
 {
+  screen_cast_session->persist_mode = SCREEN_CAST_PERSIST_MODE_NONE;
+  screen_cast_session->restored.creation_time = -1;
 }
 
 static void
@@ -594,6 +906,14 @@ gboolean
 screen_cast_init (GDBusConnection  *connection,
                   GError          **error)
 {
+  /*
+   * Ensure ShellIntrospect and DisplayStateTracker are initialized before
+   * any screencast session is created to avoid race conditions when restoring
+   * previous streams.
+   */
+  display_state_tracker_get ();
+  shell_introspect_get ();
+
   impl_connection = connection;
   gnome_screen_cast = gnome_screen_cast_new (connection);
 
diff --git a/src/screencast.h b/src/screencast.h
index e595c12..04f7616 100644
--- a/src/screencast.h
+++ b/src/screencast.h
@@ -39,6 +39,13 @@ typedef enum _ScreenCastCursorMode
   SCREEN_CAST_CURSOR_MODE_METADATA = 4,
 } ScreenCastCursorMode;
 
+typedef enum _ScreenCastPersistMode
+{
+  SCREEN_CAST_PERSIST_MODE_NONE = 0,
+  SCREEN_CAST_PERSIST_MODE_TRANSIENT = 1,
+  SCREEN_CAST_PERSIST_MODE_PERSISTENT = 2,
+} ScreenCastPersistMode;
+
 typedef struct _ScreenCastSelection
 {
   gboolean multiple;
diff --git a/src/screencastdialog.c b/src/screencastdialog.c
index d52cf7b..c8f6d2b 100644
--- a/src/screencastdialog.c
+++ b/src/screencastdialog.c
@@ -59,6 +59,7 @@ static void
 on_button_clicked_cb (GtkWidget        *button,
                       ScreenCastDialog *dialog)
 {
+  ScreenCastPersistMode persist_mode;
   g_autoptr(GPtrArray) streams = NULL;
   int response;
 
@@ -71,14 +72,16 @@ on_button_clicked_cb (GtkWidget        *button,
 
       response = GTK_RESPONSE_OK;
       streams = screen_cast_widget_get_selected_streams (screen_cast_widget);
+      persist_mode = screen_cast_widget_get_persist_mode (screen_cast_widget);
     }
   else
     {
       response = GTK_RESPONSE_CANCEL;
+      persist_mode = SCREEN_CAST_PERSIST_MODE_NONE;
       streams = NULL;
     }
 
-  g_signal_emit (dialog, signals[DONE], 0, response, streams);
+  g_signal_emit (dialog, signals[DONE], 0, response, persist_mode, streams);
 }
 
 static void
@@ -120,7 +123,8 @@ screen_cast_dialog_class_init (ScreenCastDialogClass *klass)
                                 0,
                                 NULL, NULL,
                                 NULL,
-                                G_TYPE_NONE, 2,
+                                G_TYPE_NONE, 3,
+                                G_TYPE_INT,
                                 G_TYPE_INT,
                                 G_TYPE_PTR_ARRAY);
 
@@ -143,8 +147,9 @@ screen_cast_dialog_init (ScreenCastDialog *dialog)
 }
 
 ScreenCastDialog *
-screen_cast_dialog_new (const char          *app_id,
-                        ScreenCastSelection *select)
+screen_cast_dialog_new (const char            *app_id,
+                        ScreenCastSelection   *select,
+                        ScreenCastPersistMode  persist_mode)
 {
   ScreenCastDialog *dialog;
   ScreenCastWidget *screen_cast_widget;
@@ -155,6 +160,7 @@ screen_cast_dialog_new (const char          *app_id,
   screen_cast_widget_set_allow_multiple (screen_cast_widget, select->multiple);
   screen_cast_widget_set_source_types (screen_cast_widget,
                                        select->source_types);
+  screen_cast_widget_set_persist_mode (screen_cast_widget, persist_mode);
 
   return dialog;
 }
diff --git a/src/screencastdialog.h b/src/screencastdialog.h
index 1fca470..c132ecf 100644
--- a/src/screencastdialog.h
+++ b/src/screencastdialog.h
@@ -26,5 +26,6 @@
 G_DECLARE_FINAL_TYPE (ScreenCastDialog, screen_cast_dialog,
                       SCREEN_CAST, DIALOG, GtkWindow)
 
-ScreenCastDialog * screen_cast_dialog_new (const char          *app_id,
-                                           ScreenCastSelection *select);
+ScreenCastDialog * screen_cast_dialog_new (const char            *app_id,
+                                           ScreenCastSelection   *select,
+                                           ScreenCastPersistMode  persist_mode);
diff --git a/src/screencastwidget.c b/src/screencastwidget.c
index 6f27093..089ee2a 100644
--- a/src/screencastwidget.c
+++ b/src/screencastwidget.c
@@ -56,6 +56,9 @@ struct _ScreenCastWidget
   GtkWidget *virtual_switch;
   GtkWidget *virtual_switch_label;
 
+  GtkCheckButton *persist_check;
+  ScreenCastPersistMode persist_mode;
+
   DisplayStateTracker *display_state_tracker;
   gulong monitors_changed_handler_id;
 
@@ -470,6 +473,7 @@ screen_cast_widget_class_init (ScreenCastWidgetClass *klass)
                                                  G_TYPE_BOOLEAN);
 
   gtk_widget_class_set_template_from_resource (widget_class, 
"/org/freedesktop/portal/desktop/gnome/screencastwidget.ui");
+  gtk_widget_class_bind_template_child (widget_class, ScreenCastWidget, persist_check);
   gtk_widget_class_bind_template_child (widget_class, ScreenCastWidget, source_type_switcher);
   gtk_widget_class_bind_template_child (widget_class, ScreenCastWidget, source_type);
   gtk_widget_class_bind_template_child (widget_class, ScreenCastWidget, monitor_selection);
@@ -669,3 +673,22 @@ screen_cast_widget_get_selected_streams (ScreenCastWidget *self)
 
   return g_steal_pointer (&streams);
 }
+
+void
+screen_cast_widget_set_persist_mode (ScreenCastWidget      *screen_cast_widget,
+                                     ScreenCastPersistMode  persist_mode)
+{
+  screen_cast_widget->persist_mode = persist_mode;
+
+  gtk_widget_set_visible (GTK_WIDGET (screen_cast_widget->persist_check),
+                                      persist_mode != SCREEN_CAST_PERSIST_MODE_NONE);
+}
+
+ScreenCastPersistMode
+screen_cast_widget_get_persist_mode (ScreenCastWidget *screen_cast_widget)
+{
+  if (!gtk_check_button_get_active (screen_cast_widget->persist_check))
+    return SCREEN_CAST_PERSIST_MODE_NONE;
+
+  return screen_cast_widget->persist_mode;
+}
diff --git a/src/screencastwidget.h b/src/screencastwidget.h
index 70a8e30..3fe47eb 100644
--- a/src/screencastwidget.h
+++ b/src/screencastwidget.h
@@ -38,3 +38,9 @@ void screen_cast_widget_set_source_types (ScreenCastWidget     *screen_cast_widg
                                           ScreenCastSourceType  source_types);
 
 GPtrArray *screen_cast_widget_get_selected_streams (ScreenCastWidget *self);
+
+void screen_cast_widget_set_persist_mode (ScreenCastWidget *screen_cast_widget,
+                                          ScreenCastPersistMode persist_mode);
+
+ScreenCastPersistMode
+screen_cast_widget_get_persist_mode (ScreenCastWidget *screen_cast_widget);
diff --git a/src/screencastwidget.ui b/src/screencastwidget.ui
index fbabfa7..ce1adc9 100644
--- a/src/screencastwidget.ui
+++ b/src/screencastwidget.ui
@@ -210,5 +210,13 @@
         </child>
       </object>
     </child>
+
+    <!-- Persist permission -->
+    <child>
+      <object class="GtkCheckButton" id="persist_check">
+        <property name="active">True</property>
+        <property name="label" translatable="yes">Remember this decision</property>
+      </object>
+    </child>
   </template>
 </interface>
diff --git a/src/utils.c b/src/utils.c
index b7dd472..5e0485c 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -45,3 +45,80 @@ xdg_desktop_portal_error_quark (void)
                                       G_N_ELEMENTS (xdg_desktop_portal_error_entries));
   return (GQuark) quark_volatile;
 }
+
+glong
+str_distance (const char *a,
+              const char *b)
+{
+  g_autofree gint *v0 = NULL;
+  g_autofree gint *v1 = NULL;
+  const gchar *s;
+  const gchar *t;
+  gunichar sc;
+  gunichar tc;
+  glong b_char_len;
+  glong cost;
+  glong i;
+  glong j;
+
+  /*
+  * Handle degenerate cases.
+  */
+  if (g_strcmp0 (a, b) == 0)
+    return 0;
+  else if (!*a)
+    return g_utf8_strlen (a, -1);
+  else if (!*b)
+    return g_utf8_strlen (a, -1);
+
+  b_char_len = g_utf8_strlen (b, -1);
+
+  /*
+   * Create two vectors to hold our states.
+   */
+
+  v0 = g_new0 (gint, b_char_len + 1);
+  v1 = g_new0 (gint, b_char_len + 1);
+
+  /*
+   * initialize v0 (the previous row of distances).
+   * this row is A[0][i]: edit distance for an empty a.
+   * the distance is just the number of characters to delete from b.
+   */
+  for (i = 0; i < b_char_len + 1; i++)
+    v0[i] = i;
+
+  for (i = 0, s = a; s && *s; i++, s = g_utf8_next_char(s))
+    {
+      /*
+       * Calculate v1 (current row distances) from the previous row v0.
+       */
+
+      sc = g_utf8_get_char(s);
+
+      /*
+       * first element of v1 is A[i+1][0]
+       *
+       * edit distance is delete (i+1) chars from a to match empty
+       * b.
+       */
+      v1[0] = i + 1;
+
+      /*
+       * use formula to fill in the rest of the row.
+       */
+      for (j = 0, t = b; t && *t; j++, t = g_utf8_next_char(t))
+        {
+          tc = g_utf8_get_char(t);
+          cost = (sc == tc) ? 0 : 1;
+          v1[j+1] = MIN (v1[j] + 1, MIN (v0[j+1] + 1, v0[j] + cost));
+        }
+
+      /*
+       * copy v1 (current row) to v0 (previous row) for next iteration.
+       */
+      memcpy (v0, v1, sizeof(gint) * b_char_len);
+    }
+
+  return v1[b_char_len];
+}
diff --git a/src/utils.h b/src/utils.h
index 5fdfda9..fa3f1b0 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -37,3 +37,6 @@ typedef enum {
 #define XDG_DESKTOP_PORTAL_ERROR xdg_desktop_portal_error_quark ()
 
 GQuark  xdg_desktop_portal_error_quark (void);
+
+glong str_distance (const char *a,
+                    const char *b);