// Copyright 2013 The Go Authors. All rights reserved.

// Use of this source code is governed by a BSD-style

// license that can be found in the LICENSE file.

// Package transform provides reader and writer wrappers that transform the

// bytes passing through as well as various transformations. Example

// transformations provided by other packages include normalization and

// conversion between character sets.

package transform // import "golang.org/x/text/transform"

import (

	"bytes"

	"errors"

	"io"

	"unicode/utf8"

)

var (

	// ErrShortDst means that the destination buffer was too short to

	// receive all of the transformed bytes.

	ErrShortDst = errors.New("transform: short destination buffer")

	// ErrShortSrc means that the source buffer has insufficient data to

	// complete the transformation.

	ErrShortSrc = errors.New("transform: short source buffer")

	// ErrEndOfSpan means that the input and output (the transformed input)

	// are not identical.

	ErrEndOfSpan = errors.New("transform: input and output are not identical")

	// errInconsistentByteCount means that Transform returned success (nil

	// error) but also returned nSrc inconsistent with the src argument.

	errInconsistentByteCount = errors.New("transform: inconsistent byte count returned")

	// errShortInternal means that an internal buffer is not large enough

	// to make progress and the Transform operation must be aborted.

	errShortInternal = errors.New("transform: short internal buffer")

)

// Transformer transforms bytes.

type Transformer interface {

	// Transform writes to dst the transformed bytes read from src, and

	// returns the number of dst bytes written and src bytes read. The

	// atEOF argument tells whether src represents the last bytes of the

	// input.

	//

	// Callers should always process the nDst bytes produced and account

	// for the nSrc bytes consumed before considering the error err.

	//

	// A nil error means that all of the transformed bytes (whether freshly

	// transformed from src or left over from previous Transform calls)

	// were written to dst. A nil error can be returned regardless of

	// whether atEOF is true. If err is nil then nSrc must equal len(src);

	// the converse is not necessarily true.

	//

	// ErrShortDst means that dst was too short to receive all of the

	// transformed bytes. ErrShortSrc means that src had insufficient data

	// to complete the transformation. If both conditions apply, then

	// either error may be returned. Other than the error conditions listed

	// here, implementations are free to report other errors that arise.

	Transform(dst, src []byte, atEOF bool) (nDst, nSrc int, err error)

	// Reset resets the state and allows a Transformer to be reused.

	Reset()

}

// SpanningTransformer extends the Transformer interface with a Span method

// that determines how much of the input already conforms to the Transformer.

type SpanningTransformer interface {

	Transformer

	// Span returns a position in src such that transforming src[:n] results in

	// identical output src[:n] for these bytes. It does not necessarily return

	// the largest such n. The atEOF argument tells whether src represents the

	// last bytes of the input.

	//

	// Callers should always account for the n bytes consumed before

	// considering the error err.

	//

	// A nil error means that all input bytes are known to be identical to the

	// equal len(src); the converse is not necessarily true.

	//

	// ErrEndOfSpan means that the Transformer output may differ from the

	// input after n bytes. Note that n may be len(src), meaning that the output

	// would contain additional bytes after otherwise identical output.

	// ErrShortSrc means that src had insufficient data to determine whether the

	// remaining bytes would change. Other than the error conditions listed

	// here, implementations are free to report other errors that arise.

	//

	// Calling Span can modify the Transformer state as a side effect. In

	// effect, it does the transformation just as calling Transform would, only

	// without copying to a destination buffer and only up to a point it can

	// determine the input and output bytes are the same. This is obviously more

	// limited than calling Transform, but can be more efficient in terms of

	// copying and allocating buffers. Calls to Span and Transform may be

	// interleaved.

	Span(src []byte, atEOF bool) (n int, err error)

}

// NopResetter can be embedded by implementations of Transformer to add a nop

// Reset method.

type NopResetter struct{}

// Reset implements the Reset method of the Transformer interface.

func (NopResetter) Reset() {}

// Reader wraps another io.Reader by transforming the bytes read.

type Reader struct {

	r   io.Reader

	t   Transformer

	err error

	// dst[dst0:dst1] contains bytes that have been transformed by t but

	// not yet copied out via Read.

	dst        []byte

	dst0, dst1 int

	// src[src0:src1] contains bytes that have been read from r but not

	// yet transformed through t.

	src        []byte

	src0, src1 int

	// transformComplete is whether the transformation is complete,

	// regardless of whether or not it was successful.

	transformComplete bool

}

const defaultBufSize = 4096

// NewReader returns a new Reader that wraps r by transforming the bytes read

// via t. It calls Reset on t.

func NewReader(r io.Reader, t Transformer) *Reader {

	t.Reset()

	return &Reader{

		r:   r,

		t:   t,

		dst: make([]byte, defaultBufSize),

		src: make([]byte, defaultBufSize),

	}

}

// Read implements the io.Reader interface.

func (r *Reader) Read(p []byte) (int, error) {

	n, err := 0, error(nil)

	for {

		// Copy out any transformed bytes and return the final error if we are done.

		if r.dst0 != r.dst1 {

			n = copy(p, r.dst[r.dst0:r.dst1])

			r.dst0 += n

			if r.dst0 == r.dst1 && r.transformComplete {

				return n, r.err

			}

			return n, nil

		} else if r.transformComplete {

			return 0, r.err

		}

		// Try to transform some source bytes, or to flush the transformer if we

		// are out of source bytes. We do this even if r.r.Read returned an error.

		// As the io.Reader documentation says, "process the n > 0 bytes returned

		// before considering the error".

		if r.src0 != r.src1 || r.err != nil {

			r.dst0 = 0

			r.dst1, n, err = r.t.Transform(r.dst, r.src[r.src0:r.src1], r.err == io.EOF)

			r.src0 += n

			switch {

			case err == nil:

				if r.src0 != r.src1 {

					r.err = errInconsistentByteCount

				}

				// The Transform call was successful; we are complete if we

				// cannot read more bytes into src.

				r.transformComplete = r.err != nil

				continue

			case err == ErrShortDst && (r.dst1 != 0 || n != 0):

				// Make room in dst by copying out, and try again.

				continue

			case err == ErrShortSrc && r.src1-r.src0 != len(r.src) && r.err == nil:

				// Read more bytes into src via the code below, and try again.

			default:

				r.transformComplete = true

				// The reader error (r.err) takes precedence over the

				// transformer error (err) unless r.err is nil or io.EOF.

				if r.err == nil || r.err == io.EOF {

					r.err = err

				}

				continue

			}

		}

		// Move any untransformed source bytes to the start of the buffer

		// and read more bytes.

		if r.src0 != 0 {

			r.src0, r.src1 = 0, copy(r.src, r.src[r.src0:r.src1])

		}

		n, r.err = r.r.Read(r.src[r.src1:])

		r.src1 += n

	}

}

// TODO: implement ReadByte (and ReadRune??).

// Writer wraps another io.Writer by transforming the bytes read.

// The user needs to call Close to flush unwritten bytes that may

// be buffered.

type Writer struct {

	w   io.Writer

	t   Transformer

	dst []byte

	// src[:n] contains bytes that have not yet passed through t.

	src []byte

	n   int

}

// NewWriter returns a new Writer that wraps w by transforming the bytes written

// via t. It calls Reset on t.

func NewWriter(w io.Writer, t Transformer) *Writer {

	t.Reset()

	return &Writer{

		w:   w,

		t:   t,

		dst: make([]byte, defaultBufSize),

		src: make([]byte, defaultBufSize),

	}

}

// Write implements the io.Writer interface. If there are not enough

// bytes available to complete a Transform, the bytes will be buffered

// for the next write. Call Close to convert the remaining bytes.

func (w *Writer) Write(data []byte) (n int, err error) {

	src := data

	if w.n > 0 {

		// Append bytes from data to the last remainder.

		// TODO: limit the amount copied on first try.

		n = copy(w.src[w.n:], data)

		w.n += n

		src = w.src[:w.n]

	}

	for {

		nDst, nSrc, err := w.t.Transform(w.dst, src, false)

		if _, werr := w.w.Write(w.dst[:nDst]); werr != nil {

			return n, werr

		}

		src = src[nSrc:]

		if w.n == 0 {

			n += nSrc

		} else if len(src) <= n {

			// Enough bytes from w.src have been consumed. We make src point

			// to data instead to reduce the copying.

			w.n = 0

			n -= len(src)

			src = data[n:]

			if n < len(data) && (err == nil || err == ErrShortSrc) {

				continue

			}

		}

		switch err {

		case ErrShortDst:

			// This error is okay as long as we are making progress.

			if nDst > 0 || nSrc > 0 {

				continue

			}

		case ErrShortSrc:

			if len(src) < len(w.src) {

				m := copy(w.src, src)

				// If w.n > 0, bytes from data were already copied to w.src and n

				// was already set to the number of bytes consumed.

				if w.n == 0 {

					n += m

				}

				w.n = m

				err = nil

			} else if nDst > 0 || nSrc > 0 {

				// Not enough buffer to store the remainder. Keep processing as

				// long as there is progress. Without this case, transforms that

				// require a lookahead larger than the buffer may result in an

				// error. This is not something one may expect to be common in

				// practice, but it may occur when buffers are set to small

				// sizes during testing.

				continue

			}

		case nil:

			if w.n > 0 {

				err = errInconsistentByteCount

			}

		}

		return n, err

	}

}

// Close implements the io.Closer interface.

func (w *Writer) Close() error {

	src := w.src[:w.n]

	for {

		nDst, nSrc, err := w.t.Transform(w.dst, src, true)

		if _, werr := w.w.Write(w.dst[:nDst]); werr != nil {

			return werr

		}

		if err != ErrShortDst {

			return err

		}

		src = src[nSrc:]

	}

}

type nop struct{ NopResetter }

func (nop) Transform(dst, src []byte, atEOF bool) (nDst, nSrc int, err error) {

	n := copy(dst, src)

	if n < len(src) {

		err = ErrShortDst

	}

	return n, n, err

}

func (nop) Span(src []byte, atEOF bool) (n int, err error) {

	return len(src), nil

}

type discard struct{ NopResetter }

func (discard) Transform(dst, src []byte, atEOF bool) (nDst, nSrc int, err error) {

	return 0, len(src), nil

}

var (

	// Discard is a Transformer for which all Transform calls succeed

	// by consuming all bytes and writing nothing.

	Discard Transformer = discard{}

	// Nop is a SpanningTransformer that copies src to dst.

	Nop SpanningTransformer = nop{}

)

// chain is a sequence of links. A chain with N Transformers has N+1 links and

// N+1 buffers. Of those N+1 buffers, the first and last are the src and dst

// buffers given to chain.Transform and the middle N-1 buffers are intermediate

// buffers owned by the chain. The i'th link transforms bytes from the i'th

// buffer chain.link[i].b at read offset chain.link[i].p to the i+1'th buffer

// chain.link[i+1].b at write offset chain.link[i+1].n, for i in [0, N).

type chain struct {

	link []link

	err  error

	// errStart is the index at which the error occurred plus 1. Processing

	// errStart at this level at the next call to Transform. As long as

	// errStart > 0, chain will not consume any more source bytes.

	errStart int

}

func (c *chain) fatalError(errIndex int, err error) {

	if i := errIndex + 1; i > c.errStart {

		c.errStart = i

		c.err = err

	}

}

type link struct {

	t Transformer

	// b[p:n] holds the bytes to be transformed by t.

	b []byte

	p int

	n int

}

func (l *link) src() []byte {

	return l.b[l.p:l.n]

}

func (l *link) dst() []byte {

	return l.b[l.n:]

}

// Chain returns a Transformer that applies t in sequence.

func Chain(t ...Transformer) Transformer {

	if len(t) == 0 {

		return nop{}

	}

	c := &chain{link: make([]link, len(t)+1)}

	for i, tt := range t {

		c.link[i].t = tt

	}

	// Allocate intermediate buffers.

	b := make([][defaultBufSize]byte, len(t)-1)

	for i := range b {

		c.link[i+1].b = b[i][:]

	}

	return c

}

// Reset resets the state of Chain. It calls Reset on all the Transformers.

func (c *chain) Reset() {

	for i, l := range c.link {

		if l.t != nil {

			l.t.Reset()

		}

		c.link[i].p, c.link[i].n = 0, 0

	}

}

// TODO: make chain use Span (is going to be fun to implement!)

// Transform applies the transformers of c in sequence.

func (c *chain) Transform(dst, src []byte, atEOF bool) (nDst, nSrc int, err error) {

	// Set up src and dst in the chain.

	srcL := &c.link[0]

	dstL := &c.link[len(c.link)-1]

	srcL.b, srcL.p, srcL.n = src, 0, len(src)

	dstL.b, dstL.n = dst, 0

	var lastFull, needProgress bool // for detecting progress

	// i is the index of the next Transformer to apply, for i in [low, high].

	// low is the lowest index for which c.link[low] may still produce bytes.

	// high is the highest index for which c.link[high] has a Transformer.

	// The error returned by Transform determines whether to increase or

	// decrease i. We try to completely fill a buffer before converting it.

	for low, i, high := c.errStart, c.errStart, len(c.link)-2; low <= i && i <= high; {

		in, out := &c.link[i], &c.link[i+1]