encoding/json: detect circular data structures when encoding

[bep]

The following program panics.

OS: Linux
Go version: tip and 1.4.2

I searched, but didn't find this in here.

/cc @dvyukov go-fuzz

package main

import (
    "html/template"
    "io/ioutil"
)

func main() {
    t, err := template.New("foo").Parse(data)
    if err != nil {
        return
    }

    a := &A{}
    a.B1 = &B{a}
    ping := &Ping{a}

    t.Execute(ioutil.Discard, ping)
}

var data = "<script>{{ .Pong }}</script>"

type Ping struct {
    Pong *A
}

type A struct {
    B1 *B
}

type B struct {
    A1 *A
}

runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

runtime stack:
runtime.throw(0x5e7490, 0xe)
    /home/bep/dev/golang/go/src/runtime/panic.go:543 +0x96
runtime.newstack()
    /home/bep/dev/golang/go/src/runtime/stack1.go:744 +0xb3f
runtime.morestack()
    /home/bep/dev/golang/go/src/runtime/asm_amd64.s:330 +0x82

goroutine 1 [stack growth]:
encoding/json.(*structEncoder).encode(0xc208012e40, 0xc208095810, 0x585560, 0xc208028038, 0xd9, 0x0)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:569 fp=0xc2280fa280 sp=0xc2280fa278
encoding/json.(*structEncoder).(encoding/json.encode)-fm(0xc208095810, 0x585560, 0xc208028038, 0xd9, 0x5bf900)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:598 +0x58 fp=0xc2280fa2b8 sp=0xc2280fa280
encoding/json.typeEncoder.func1(0xc208095810, 0x585560, 0xc208028038, 0xd9, 0xc208028000)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:336 +0x6d fp=0xc2280fa2f0 sp=0xc2280fa2b8
encoding/json.(*ptrEncoder).encode(0xc208028088, 0xc208095810, 0x531e60, 0xc208028040, 0xd6, 0x4c5200)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:706 +0xed fp=0xc2280fa340 sp=0xc2280fa2f0
encoding/json.(*ptrEncoder).(encoding/json.encode)-fm(0xc208095810, 0x531e60, 0xc208028040, 0xd6, 0x0)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:711 +0x58 fp=0xc2280fa378 sp=0xc2280fa340
encoding/json.(*structEncoder).encode(0xc208012f30, 0xc208095810, 0x585620, 0xc208028040, 0xd9, 0x4aad00)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:584 +0x2c3 fp=0xc2280fa520 sp=0xc2280fa378
encoding/json.(*structEncoder).(encoding/json.encode)-fm(0xc208095810, 0x585620, 0xc208028040, 0xd9, 0xc208028000)
    /home/bep/dev/golang/go/src/encoding/json/encode.go:598 +0x58 fp=0xc2280fa558 sp=0xc2280fa520
encoding/json.(*ptrEncoder).encode(0xc208028090, 0xc208095810, 0x531ec0, 0xc208028038, 0xd6, 0x4c5200)
    /home/bep/dev/g

[dvyukov]

Isn't it a documented encoding/json limitation? What would be the expected behavior of such program?

[bep]

If it is a documented limitation I would strongly expect it to return an informative ERROR - and not go into a glowing hot CPU and then panic.

It should be possible to detect these cycles earlier.

In this case it's triggered from a Go template -- go template end users don't understand cyclic object graphs until it's spelled out for them.

[bep]

The json package says:

JSON cannot represent cyclic data structures and Marshal does not
handle them.  Passing cyclic structures to Marshal will result in
an infinite recursion.

The template package says:

 See package json to understand how non-string content is marshalled for embedding in JavaScript contexts. 

So, I guess you are kind of correct when you say that this is a documented limitation ... But one could argue that this opens the html templates up for code injection (DDoS), which the documentation says it protects against.

[adg]

I don't think it's reasonable to expect the template package to mitigate all possible forms of pathological input. I'm sure it's possible, but am having a hard time imagining a real program that would allow a user to construct the circular graph that triggers this behaviour.

To mitigate this issue we would necessarily complicate and slow down the JSON encoder, which is something we have decided not to do.

Thanks for the report.

[bep]

Up to you.

BTW, this issue was found by a user using a real program. He didn't have to "construct the circular graph", it was there in the context. Maybe it shouldn't have been, but circular refs are very common -- I wouldn't call them "pathological input".

[adg]

How could it be anything other than pathological? What is a reasonable way to JSON encode a circular data structure?

[bradfitz]

It wouldn't be too hard or slow down the JSON encoder much to catch circular references. (and if we catch one, we can just return an error)

I think we can leave this open.

[bep]

That I agree about.

The Go program in question is Hugo, a static site generator. It uses Go templates. In the template context is the Site. Site has a list of Pages; each Page has a reference to the Site it belongs to.

So a person does this in a template (gohugoio/hugo#1123):

<script>
{{ .Site }}
</script>

And BAM!

I would agree that this usage is "pathological", but people do stupid (and some do evil) things.

And from Hugo's point of view, to fix this, we must remove the circular reference from Page (and maybe some other), but that would make the software useless.