Woocommerce product permalink not working

Well, WooCommerce documentation clearly states

Please note: The product custom base should not conflict with the taxonomy permalink bases. If you set the product base to ‘shop’ for example, you should not set the product category base to ‘shop’ too as this will not be unique and will conflict. WordPress requires something unique so it can distinguish categories from products.

https://docs.woocommerce.com/document/permalinks/#section-2

I think this may be a generic WP level rewrite issue: how do you match things across entity types (posts and taxonomies). There are big discussions on uh… rewriting the core rewrite systems because it has become a bottleneck https://core.trac.wordpress.org/ticket/36292 but it’s probably a long-winded project.