WooCommerce product permalink structure using add_rewrite_rule() with parent/child/ page

I'm attempting to customize the permalink structure for WooCommerce products.

I've tried implementing a solution using add_rewrite_rule() but haven't been successful. Currently, the links are generated as:

• my-website.com/shop/product/product_name-sku

but I want them to be structured as:

• my-website.com/shop/parent-cat/child-cat/product_name-sku

I'm struggling to understand how to incorporate get_terms() with parent and child categories.

My code snippet so far:

add_filter('post_type_link', 'custom_product_permalink', 1, 2);

function custom_product_permalink($link, $post) {
    if ($post->post_type == 'product') {
        // Convert the entire URL to lowercase
        return strtolower(home_url('shop/product/' . $post->post_name . '-' . get_post_meta($post->ID, '_sku', true) . '/'));
    } else {
        return $link;
    }
}

add_action('init', 'custom_product_permalink_rewrite_rules');

function custom_product_permalink_rewrite_rules() {
    add_rewrite_rule(
        'shop/product/([^/]+)-([^/]+)/?$',
        'index.php?post_type=product&name=$matches[1]&sku=$matches[2]',
        'top'
    );

    flush_rewrite_rules();
}

I'm new to advanced WordPress coding, any guidance or assistance would be greatly appreciated.

The custom_product_permalink() function can be modified to find and include the full category slug (with parent slugs) and exclude the "product" string (which also changes the rewrite rule):

add_filter('post_type_link', 'custom_product_permalink', 1, 2);

function custom_product_permalink($link, $post) {
    if ($post->post_type == 'product') {
        $cat_tax = 'product_cat';
        // Find the product category IDs
        $cat_ids = wp_get_post_terms($post->ID, $cat_tax, ['fields' => 'ids']);
        $cat_full_slug = '';
        if (is_array($cat_ids) && !empty($cat_ids)) {
            // Build a full hierarchical category slug
            $cat_full_slug = get_term_parents_list($cat_ids[0], $cat_tax, [
                'format' => 'slug',
                'separator' => '/',
                'link' => false,
                'inclusive' =>true
            ]);
        }
        // Convert the entire URL to lowercase
        return strtolower(home_url('shop/' . $cat_full_slug .
                                   $post->post_name . '-' .
                                   get_post_meta($post->ID, '_sku', true) . '/'));
    } else {
        return $link;
    }
}

add_action('init', 'custom_product_permalink_rewrite_rules');

function custom_product_permalink_rewrite_rules() {
    add_rewrite_rule(
        'shop/.+/([^/]+)-([^/]+)/?$',
        'index.php?post_type=product&name=$matches[1]&sku=$matches[2]',
        'top'
    );

    flush_rewrite_rules();
}

Note that a product should have at least one category for this to work. In cases when there are multiple categories only the first one returned by wp_get_post_terms() is used. The _sku is also required and it cannot contain -.