Stacked versioning broken when not using `:path` version method

Upgrading from 0.18.0 to 0.19.0 breaks our app when we use :accept_version_header, version arrays for fallbacks, and a catch-all. I wrote this series of tests (at bottom) to verify, and all non-path catch-all tests fail.

After extensive investigation, it looks like :path versioning works because it matches using the @optimized_router immediately based on the /:version/:path pattern. When using other versioning methods and stacked versioning, version is not correctly found with the optimized router since the path pattern does not include the version. Before 0.19.0, this worked fine because the response would fall back to Router#rotation, which properly matches the correct version. After 0.19.0, the catch-all match has been prioritized over Router#rotation and prevents a correct version match.

Two approaches that could address this:

1. Change the order of the catch-all match (meh). If we could move the * match to after the #rotation match, that could make things work.
2. Change how optimized router works to be the same independent of versioning method (ideal). Versioning would work best if we normalized how versions manifest themselves as early in the request as possible so that everything else can be agnostic to the chosen version method.

The best option would be #2, but I wanted to get some feedback before going too deep with either option. In the meantime on our app, we'll likely configure our app to use :path versioning, and then add some middleware that transforms any header versioned requests into path versioned requests.

describe Grape::API do
  subject { Class.new(Grape::API) }

  def app
    subject
  end

  before do
    api1 = Class.new(Grape::API)
    api1.version ['v3', 'v2', 'v1'], version_options
    api1.get('all') { 'v1' }
    api1.get('only_v1') { 'only_v1' }

    api2 = Class.new(Grape::API)
    api2.version ['v3', 'v2'], version_options
    api2.get('all') { 'v2' }
    api2.get('only_v2') { 'only_v2' }

    api3 = Class.new(Grape::API)
    api3.version 'v3', version_options
    api3.get('all') { 'v3' }

    app.mount api3
    app.mount api2
    app.mount api1
  end

  shared_examples 'version fallback' do
    it 'returns the correct version' do
      versioned_get '/all', 'v1', version_options
      expect(last_response.status).to eq(200)
      expect(last_response.body).to eq('v1')

      versioned_get '/all', 'v2', version_options
      expect(last_response.status).to eq(200)
      expect(last_response.body).to eq('v2')

      versioned_get '/all', 'v3', version_options
      expect(last_response.status).to eq(200)
      expect(last_response.body).to eq('v3')

      versioned_get '/only_v1', 'v2', version_options
      expect(last_response.status).to eq(200)
      expect(last_response.body).to eq('only_v1')

      versioned_get '/only_v1', 'v3', version_options
      expect(last_response.status).to eq(200)
      expect(last_response.body).to eq('only_v1')

      versioned_get '/only_v2', 'v3', version_options
      expect(last_response.status).to eq(200)
      expect(last_response.body).to eq('only_v2')
    end
  end

  context 'with catch-all' do
    before do
      app.route :any, '*path' do
        error!("Unrecognized request path: #{params[:path]} - #{env['PATH_INFO']}#{env['SCRIPT_NAME']}", 404)
      end
    end

    shared_examples 'catch-all' do
      it 'returns a 404' do
        get '/foobar'
        expect(last_response.status).to eq(404)
        expect(last_response.body).to eq('Unrecognized request path: foobar - /foobar')
      end
    end

    context 'using path' do
      let(:version_options) { { using: :path } }

      it_behaves_like 'version fallback'
      it_behaves_like 'catch-all'
    end

    context 'using param' do
      let(:version_options) { { using: :param } }

      it_behaves_like 'version fallback'
      it_behaves_like 'catch-all'
    end

    context 'using accept_version_header' do
      let(:version_options) { { using: :accept_version_header } }

      it_behaves_like 'version fallback'
      it_behaves_like 'catch-all'
    end

    context 'using header' do
      let(:version_options) { { using: :header, vendor: 'test' } }

      it_behaves_like 'version fallback'
      it_behaves_like 'catch-all'
    end
  end

  context 'without catch-all' do
    context 'using path' do
      let(:version_options) { { using: :path } }

      it_behaves_like 'version fallback'
    end

    context 'using param' do
      let(:version_options) { { using: :param } }

      it_behaves_like 'version fallback'
    end

    context 'using accept_version_header' do
      let(:version_options) { { using: :accept_version_header } }

      it_behaves_like 'version fallback'
    end

    context 'using header' do
      let(:version_options) { { using: :header, vendor: 'test' } }

      it_behaves_like 'version fallback'
    end
  end
end

Start by reproducing the pasted stacked-versioning examples for path, param, accept_version_header, and header methods, then inspect optimized_router and Router#rotation. The fix is complete when non-path version fallbacks work with a catch-all while unmatched paths still return the documented 404 response.