Circular references cause stack overflow

[christianklotz]

After coming across the same or similar issue to go-swagger #537 I looked into it a little further. If I understand it correctly expander.go has a check for circular references.

pRefs := strings.Join(parentRefs, ",")
pRefs += ","
if strings.Contains(pRefs, currentSchema.Ref.String()+",") {
  break
}

However it seems like it's appending the current schema too late. I tested it with the swagger definition below which has a Book definition with related Book items, and the overall definition structure is Store > Category > Book.

fmt.Println(pRefs) // #/definitions/Store,#/definitions/Category,

fmt.Println(currentSchema.Ref.String()+",") // #/definitions/Book,

It only appears to happen if the circular reference a few levels deep. For instance, if the store has books directly without categories, it's fine.

Swagger Definition

swagger: "2.0"
info:
  title: Swagger Sample
  description: Sample API Playground.
  version: 1.0.0
basePath: /v1
schemes:
- http
consumes:
- application/vdn.sample.v1+json
produces:
- application/vdn.sample.v1+json

paths:
  /books:
    get:
      summary: List all books
      operationId: listBooks
      tags:
        - books
      responses:
        200:
          headers:
            Link:
              type: string
          description: An array of books
          schema:
            type: array
            items:
              $ref: "#/definitions/Book"
        default:
          description: generic error response
          schema:
            $ref: "#/definitions/Error"

definitions:
  # Store
  Store:
    type: object
    properties:
      title:
        type: string
        example: Book Shop
      categories:
        type: array
        items:
          $ref: "#/definitions/Category"

  # Category
  Category:
    type: object
    properties:
      title:
        type: string
        example: Drama
      books:
        type: array
        items:
          $ref: "#/definitions/Book"

  # Book
  Book:
    type: object
    required:
      - title
      - summary
    properties:
      title:
        type: string
        example: Winnie the Pooh
      summary:
        type: string
        example: Famous children's book
      # related_books is causing an infinite loop
      related_books:
        type: array
        items:
          $ref: "#/definitions/Book"


  # Error
  Error:
    type: object
    readOnly: true
    properties:
      code:
        type: integer
        format: int64
        example: 400
      message:
        type: string
        example: Unexpected error
    required:
      - message

[pytlesk4]

Hmm intersting.

So, this is where we actually append the current schema ref:

https://github.com/go-openapi/spec/blob/master/expander.go#L438

The snippet above isn't actually appending the current schema ref, it is just checking to make sure that the schema hasn't already been dereferenced.

fmt.Println(pRefs) // #/definitions/Store,#/definitions/Category,
fmt.Println(currentSchema.Ref.String()+",") // #/definitions/Book,

So really what is happening here, is pRefs doesn't contain #/definitions/Book, therefore this is the first time we are encountering it, so try to dereference it. After that, then append currentSchema.Ref.String()// #/definitions/Book to the parentRefs array.

Does that make sense?

I am going to investigate this more though, as you could be correct I might be doing the append too late.

[christianklotz]

Yes, it makes sense indeed. I also looked into it a bit further using the following test.

func TestIssue3(t *testing.T) {
    doc, err := jsonDoc("fixtures/expansion/issue3.json")
    assert.NoError(t, err)

    spec := new(Swagger)
    err = json.Unmarshal(doc, spec)
    assert.NoError(t, err)

    err = ExpandSpec(spec)
    assert.NoError(t, err)
}

See issue3.json gist for the spec.

A bit of logging reveals that expanding Store → Category → Book works as expected, avoiding re-expanding Book. However when it expands Category, it hits Book and tries expanding the items of related_books without #/definitions/Book being part of parentRefs.

expand schema [#/definitions/Store] ()
expand title
expand schema [#/definitions/Store] ()
expand categories
expand schema [#/definitions/Store] ()
expand items
expand schema [#/definitions/Store] (#/definitions/Category)
expand title
expand schema [#/definitions/Store #/definitions/Category] ()
expand books
expand schema [#/definitions/Store #/definitions/Category] ()
expand items
expand schema [#/definitions/Store #/definitions/Category] (#/definitions/Book)
expand title
expand schema [#/definitions/Store #/definitions/Category #/definitions/Book] ()
expand summary
expand schema [#/definitions/Store #/definitions/Category #/definitions/Book] ()
expand related_books
expand schema [#/definitions/Store #/definitions/Category #/definitions/Book] ()
expand items
expand schema [#/definitions/Store #/definitions/Category #/definitions/Book] (#/definitions/Book)
expand schema [#/definitions/Category] ()
expand books
expand schema [#/definitions/Category] ()
expand items
expand schema [#/definitions/Category] ()
expand title
expand schema [#/definitions/Category] ()
expand summary
expand schema [#/definitions/Category] ()
expand related_books
expand schema [#/definitions/Category] ()
expand items
expand schema [#/definitions/Category] (#/definitions/Book)
expand title
expand schema [#/definitions/Category #/definitions/Book] ()
expand summary
expand schema [#/definitions/Category #/definitions/Book] ()
expand related_books
expand schema [#/definitions/Category #/definitions/Book] ()
expand items
expand schema [#/definitions/Category #/definitions/Book] ()
expand summary
expand schema [#/definitions/Category #/definitions/Book] ()
expand related_books
expand schema [#/definitions/Category #/definitions/Book] ()
expand items
expand schema [#/definitions/Category #/definitions/Book] ()
expand related_books
expand schema [#/definitions/Category #/definitions/Book] ()
expand items
expand schema [#/definitions/Category #/definitions/Book] ()
...

[christianklotz]

Actually, looking at the logs properly again it seems more of an issue that the schema for is not passed properly when comes to expanding #/definitions/Book for the second time, it's always ""

Edit: I don't know the internals that well but something else in the logs I wondered about: whereas the #/definitions/Book gets passed in the Store → Category → Book scenario as soon as the Category.books attribute is expanded, in the other scenario it only seems to pass it once hitting related_books of Category.books, not Category.books.

[christianklotz]

After digging a bit deeper I think I now at least know why it's not breaking the circular expansion.

When expanding the Store it first calls expandItems on the categories property which in turn calls expandSchema:

...

expand property 'categories'
expandSchema parentRefs: [#/definitions/Store], schema.Ref.String(): ""
before expandItems
expandSchema parentRefs: [#/definitions/Store], schema.Ref.String(): #/definitions/Category

...

expand property 'books' (of Category)
expandSchema parentRefs: [#/definitions/Store #/definitions/Category], schema.Ref.String(): ""
before expand items
expandSchema parentRefs: [#/definitions/Store #/definitions/Category], schema.Ref.String(): #/definitions/Book

...

When expanding Category after finishing the expansion of Store it behaves differently

...

expand property 'books' (of Category)
expandSchema parentRefs: [#/definitions/Category], schema.Ref.String(): ""
before expand items
expandSchema parentRefs: [#/definitions/Category], schema.Ref.String(): "" <-- shouldn't this be #/definitions/Book?

...

As a result the following statement from expander.go is never true, hence it doesn't break the cycle.

    if schema.Ref.String() != "" {
      ...
      parentRefs = append(parentRefs, currentSchema.Ref.String())
      ...
    }

So my best guess at this point is that the currentSchema of Category.books.items is set wrongly for some reason 🤔

[christianklotz]

Just to throw in one more observation. After running it again and spec first expanding Category → Book, then processing Book and only after that expanding Store → Category → Book it shows the same behaviour as described in the previous comment but this time when expanding Store, or to be precise the second time a property of type Book is processed.

› expand related_books: 
  expandSchema parentRefs: [#/definitions/Store #/definitions/Category #/definitions/Book], schema.Ref: ''
  expandItems › expandSchema parentRefs: [#/definitions/Store #/definitions/Category #/definitions/Book], schema.Ref: ''

However, since it's now expanding in a different order and getting stuck within expanding Store I wondered if you keep track of the already expanded schemas that could somehow affect the schema passed into expandSchema the second time a definition gets expanded?

[pytlesk4]

Interesting, I am going to take a look at this more tomorrow.

[christianklotz]

@pytlesk4 did you have a chance to look at it? I might also have some time later this week to try getting my head around it. But please let me know if there's anything specific I can help with.

[pytlesk4]

@christianklotz trying to make time for it, just busy with other things at the moment. By all means if you get to it, and can figure it out, that would be awesome. Just let me know, and I will do the same. Also, don't hesitate to ask any questions: https://slackin.goswagger.io/!

[pytlesk4]

Looking at this today, unless you have started on this @christianklotz ?

[pytlesk4]

@christianklotz Fixed, need to update the tests, but will be pushing this soon!

[christianklotz]

@pytlesk4 just wanted to say thanks for fixing this. Really appreciated!