// Copyright 2011 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 norm

import "unicode/utf8"

const (

	maxNonStarters = 30

	// The maximum number of characters needed for a buffer is

	// maxNonStarters + 1 for the starter + 1 for the GCJ

	maxBufferSize    = maxNonStarters + 2

	maxNFCExpansion  = 3  // NFC(0x1D160)

	maxNFKCExpansion = 18 // NFKC(0xFDFA)

	maxByteBufferSize = utf8.UTFMax * maxBufferSize // 128

)

// ssState is used for reporting the segment state after inserting a rune.

// It is returned by streamSafe.next.

type ssState int

const (

	// Indicates a rune was successfully added to the segment.

	ssSuccess ssState = iota

	// Indicates a rune starts a new segment and should not be added.

	ssStarter

	// Indicates a rune caused a segment overflow and a CGJ should be inserted.

	ssOverflow

)

// streamSafe implements the policy of when a CGJ should be inserted.

type streamSafe uint8

// first inserts the first rune of a segment. It is a faster version of next if

// it is known p represents the first rune in a segment.

func (ss *streamSafe) first(p Properties) {

	*ss = streamSafe(p.nTrailingNonStarters())

}

// insert returns a ssState value to indicate whether a rune represented by p

// can be inserted.

func (ss *streamSafe) next(p Properties) ssState {

	if *ss > maxNonStarters {

		panic("streamSafe was not reset")

	}

	n := p.nLeadingNonStarters()

	if *ss += streamSafe(n); *ss > maxNonStarters {

		*ss = 0

		return ssOverflow

	}

	// The Stream-Safe Text Processing prescribes that the counting can stop

	// as soon as a starter is encountered. However, there are some starters,

	// like Jamo V and T, that can combine with other runes, leaving their

	// successive non-starters appended to the previous, possibly causing an

	// overflow. We will therefore consider any rune with a non-zero nLead to

	// be a non-starter. Note that it always hold that if nLead > 0 then

	// nLead == nTrail.

	if n == 0 {

		*ss = streamSafe(p.nTrailingNonStarters())

		return ssStarter

	}

	return ssSuccess

}

// backwards is used for checking for overflow and segment starts

// when traversing a string backwards. Users do not need to call first

// for the first rune. The state of the streamSafe retains the count of

// the non-starters loaded.

func (ss *streamSafe) backwards(p Properties) ssState {

	if *ss > maxNonStarters {

		panic("streamSafe was not reset")

	}

	c := *ss + streamSafe(p.nTrailingNonStarters())

	if c > maxNonStarters {

		return ssOverflow

	}

	*ss = c

	if p.nLeadingNonStarters() == 0 {

		return ssStarter

	}

	return ssSuccess

}

func (ss streamSafe) isMax() bool {

	return ss == maxNonStarters

}

// GraphemeJoiner is inserted after maxNonStarters non-starter runes.

const GraphemeJoiner = "\u034F"

// reorderBuffer is used to normalize a single segment.  Characters inserted with

// insert are decomposed and reordered based on CCC. The compose method can

// be used to recombine characters.  Note that the byte buffer does not hold

// the UTF-8 characters in order.  Only the rune array is maintained in sorted

// order. flush writes the resulting segment to a byte array.

type reorderBuffer struct {

	rune  [maxBufferSize]Properties // Per character info.

	byte  [maxByteBufferSize]byte   // UTF-8 buffer. Referenced by runeInfo.pos.

	nbyte uint8                     // Number or bytes.

	ss    streamSafe                // For limiting length of non-starter sequence.

	nrune int                       // Number of runeInfos.

	f     formInfo

	src      input

	nsrc     int

	tmpBytes input

	out    []byte

	flushF func(*reorderBuffer) bool

}

func (rb *reorderBuffer) init(f Form, src []byte) {

	rb.f = *formTable[f]

	rb.src.setBytes(src)

	rb.nsrc = len(src)

	rb.ss = 0

}

func (rb *reorderBuffer) initString(f Form, src string) {

	rb.f = *formTable[f]

	rb.src.setString(src)

	rb.nsrc = len(src)

	rb.ss = 0

}

func (rb *reorderBuffer) setFlusher(out []byte, f func(*reorderBuffer) bool) {

	rb.out = out

	rb.flushF = f

}

// reset discards all characters from the buffer.

func (rb *reorderBuffer) reset() {

	rb.nrune = 0

	rb.nbyte = 0

}

func (rb *reorderBuffer) doFlush() bool {

	if rb.f.composing {

		rb.compose()

	}

	res := rb.flushF(rb)

	rb.reset()

	return res

}

// appendFlush appends the normalized segment to rb.out.

func appendFlush(rb *reorderBuffer) bool {

	for i := 0; i < rb.nrune; i++ {

		start := rb.rune[i].pos

		end := start + rb.rune[i].size

		rb.out = append(rb.out, rb.byte[start:end]...)

	}

	return true

}

// flush appends the normalized segment to out and resets rb.

func (rb *reorderBuffer) flush(out []byte) []byte {

	for i := 0; i < rb.nrune; i++ {

		start := rb.rune[i].pos

		end := start + rb.rune[i].size

		out = append(out, rb.byte[start:end]...)

	}

	rb.reset()

	return out

}

// flushCopy copies the normalized segment to buf and resets rb.

// It returns the number of bytes written to buf.

func (rb *reorderBuffer) flushCopy(buf []byte) int {

	p := 0

	for i := 0; i < rb.nrune; i++ {

		runep := rb.rune[i]

		p += copy(buf[p:], rb.byte[runep.pos:runep.pos+runep.size])

	}

	rb.reset()

	return p

}

// insertOrdered inserts a rune in the buffer, ordered by Canonical Combining Class.

// It returns false if the buffer is not large enough to hold the rune.

// It is used internally by insert and insertString only.

func (rb *reorderBuffer) insertOrdered(info Properties) {

	n := rb.nrune

	b := rb.rune[:]

	cc := info.ccc

	if cc > 0 {

		// Find insertion position + move elements to make room.

		for ; n > 0; n-- {

			if b[n-1].ccc <= cc {

				break

			}

			b[n] = b[n-1]

		}

	}

	rb.nrune += 1

	pos := uint8(rb.nbyte)

	rb.nbyte += utf8.UTFMax

	info.pos = pos

	b[n] = info

}

// insertErr is an error code returned by insert. Using this type instead

// of error improves performance up to 20% for many of the benchmarks.

type insertErr int

const (

	iSuccess insertErr = -iota

	iShortDst

	iShortSrc

)

// insertFlush inserts the given rune in the buffer ordered by CCC.

// If a decomposition with multiple segments are encountered, they leading

// ones are flushed.

// It returns a non-zero error code if the rune was not inserted.

func (rb *reorderBuffer) insertFlush(src input, i int, info Properties) insertErr {

	if rune := src.hangul(i); rune != 0 {

		rb.decomposeHangul(rune)

		return iSuccess

	}

	if info.hasDecomposition() {

		return rb.insertDecomposed(info.Decomposition())

	}

	rb.insertSingle(src, i, info)

	return iSuccess

}

// insertUnsafe inserts the given rune in the buffer ordered by CCC.

// It is assumed there is sufficient space to hold the runes. It is the

// responsibility of the caller to ensure this. This can be done by checking

// the state returned by the streamSafe type.

func (rb *reorderBuffer) insertUnsafe(src input, i int, info Properties) {

	if rune := src.hangul(i); rune != 0 {

		rb.decomposeHangul(rune)

	}

	if info.hasDecomposition() {

		// TODO: inline.

		rb.insertDecomposed(info.Decomposition())

	} else {

		rb.insertSingle(src, i, info)

	}

}

// insertDecomposed inserts an entry in to the reorderBuffer for each rune

// in dcomp. dcomp must be a sequence of decomposed UTF-8-encoded runes.

// It flushes the buffer on each new segment start.

func (rb *reorderBuffer) insertDecomposed(dcomp []byte) insertErr {

	rb.tmpBytes.setBytes(dcomp)

	// As the streamSafe accounting already handles the counting for modifiers,

	// we don't have to call next. However, we do need to keep the accounting

	// intact when flushing the buffer.

	for i := 0; i < len(dcomp); {

		info := rb.f.info(rb.tmpBytes, i)

		if info.BoundaryBefore() && rb.nrune > 0 && !rb.doFlush() {

			return iShortDst

		}

		i += copy(rb.byte[rb.nbyte:], dcomp[i:i+int(info.size)])

		rb.insertOrdered(info)

	}

	return iSuccess

}

// insertSingle inserts an entry in the reorderBuffer for the rune at

// position i. info is the runeInfo for the rune at position i.

func (rb *reorderBuffer) insertSingle(src input, i int, info Properties) {

	src.copySlice(rb.byte[rb.nbyte:], i, i+int(info.size))

	rb.insertOrdered(info)

}

// insertCGJ inserts a Combining Grapheme Joiner (0x034f) into rb.

func (rb *reorderBuffer) insertCGJ() {

	rb.insertSingle(input{str: GraphemeJoiner}, 0, Properties{size: uint8(len(GraphemeJoiner))})

}

// appendRune inserts a rune at the end of the buffer. It is used for Hangul.

func (rb *reorderBuffer) appendRune(r rune) {

	bn := rb.nbyte

	sz := utf8.EncodeRune(rb.byte[bn:], rune(r))

	rb.nbyte += utf8.UTFMax

	rb.rune[rb.nrune] = Properties{pos: bn, size: uint8(sz)}

	rb.nrune++

}

// assignRune sets a rune at position pos. It is used for Hangul and recomposition.

func (rb *reorderBuffer) assignRune(pos int, r rune) {

	bn := rb.rune[pos].pos

	sz := utf8.EncodeRune(rb.byte[bn:], rune(r))

	rb.rune[pos] = Properties{pos: bn, size: uint8(sz)}

}

// runeAt returns the rune at position n. It is used for Hangul and recomposition.

func (rb *reorderBuffer) runeAt(n int) rune {

	inf := rb.rune[n]

	r, _ := utf8.DecodeRune(rb.byte[inf.pos : inf.pos+inf.size])

	return r

}

// bytesAt returns the UTF-8 encoding of the rune at position n.

// It is used for Hangul and recomposition.

func (rb *reorderBuffer) bytesAt(n int) []byte {

	inf := rb.rune[n]

	return rb.byte[inf.pos : int(inf.pos)+int(inf.size)]

}

// For Hangul we combine algorithmically, instead of using tables.

const (

	hangulBase  = 0xAC00 // UTF-8(hangulBase) -> EA B0 80

	hangulBase0 = 0xEA

	hangulBase1 = 0xB0

	hangulBase2 = 0x80

	hangulEnd  = hangulBase + jamoLVTCount // UTF-8(0xD7A4) -> ED 9E A4

	hangulEnd0 = 0xED

	hangulEnd1 = 0x9E

	hangulEnd2 = 0xA4

	jamoLBase  = 0x1100 // UTF-8(jamoLBase) -> E1 84 00

	jamoLBase0 = 0xE1

	jamoLBase1 = 0x84

	jamoLEnd   = 0x1113

	jamoVBase  = 0x1161

	jamoVEnd   = 0x1176

	jamoTBase  = 0x11A7

	jamoTEnd   = 0x11C3

	jamoTCount   = 28

	jamoVCount   = 21

	jamoVTCount  = 21 * 28

	jamoLVTCount = 19 * 21 * 28

)

const hangulUTF8Size = 3

func isHangul(b []byte) bool {

	if len(b) < hangulUTF8Size {

		return false

	}

	b0 := b[0]

	if b0 < hangulBase0 {

		return false

	}

	b1 := b[1]

	switch {

	case b0 == hangulBase0:

		return b1 >= hangulBase1

	case b0 < hangulEnd0:

		return true

	case b0 > hangulEnd0:

		return false

	case b1 < hangulEnd1:

		return true

	}

	return b1 == hangulEnd1 && b[2] < hangulEnd2

}

func isHangulString(b string) bool {

	if len(b) < hangulUTF8Size {

		return false

	}

	b0 := b[0]

	if b0 < hangulBase0 {

		return false

	}

	b1 := b[1]

	switch {

	case b0 == hangulBase0:

		return b1 >= hangulBase1

	case b0 < hangulEnd0:

		return true

	case b0 > hangulEnd0:

		return false

	case b1 < hangulEnd1:

		return true

	}

	return b1 == hangulEnd1 && b[2] < hangulEnd2

}

// Caller must ensure len(b) >= 2.

func isJamoVT(b []byte) bool {

	// True if (rune & 0xff00) == jamoLBase

	return b[0] == jamoLBase0 && (b[1]&0xFC) == jamoLBase1

}

func isHangulWithoutJamoT(b []byte) bool {

	c, _ := utf8.DecodeRune(b)

	c -= hangulBase

	return c < jamoLVTCount && c%jamoTCount == 0

}

// decomposeHangul writes the decomposed Hangul to buf and returns the number

// of bytes written.  len(buf) should be at least 9.

func decomposeHangul(buf []byte, r rune) int {

	const JamoUTF8Len = 3

	r -= hangulBase

	x := r % jamoTCount

	r /= jamoTCount

	utf8.EncodeRune(buf, jamoLBase+r/jamoVCount)

	utf8.EncodeRune(buf[JamoUTF8Len:], jamoVBase+r%jamoVCount)

	if x != 0 {

		utf8.EncodeRune(buf[2*JamoUTF8Len:], jamoTBase+x)

		return 3 * JamoUTF8Len

	}

	return 2 * JamoUTF8Len

}

// decomposeHangul algorithmically decomposes a Hangul rune into

// its Jamo components.

// See https://unicode.org/reports/tr15/#Hangul for details on decomposing Hangul.

func (rb *reorderBuffer) decomposeHangul(r rune) {

	r -= hangulBase

	x := r % jamoTCount

	r /= jamoTCount

	rb.appendRune(jamoLBase + r/jamoVCount)

	rb.appendRune(jamoVBase + r%jamoVCount)

	if x != 0 {

		rb.appendRune(jamoTBase + x)

	}

}

// combineHangul algorithmically combines Jamo character components into Hangul.

// See https://unicode.org/reports/tr15/#Hangul for details on combining Hangul.

func (rb *reorderBuffer) combineHangul(s, i, k int) {

	b := rb.rune[:]

	bn := rb.nrune

	for ; i < bn; i++ {

		cccB := b[k-1].ccc

		cccC := b[i].ccc

		if cccB == 0 {

			s = k - 1

		}

		if s != k-1 && cccB >= cccC {

			// b[i] is blocked by greater-equal cccX below it

			b[k] = b[i]

			k++

		} else {

			l := rb.runeAt(s) // also used to compare to hangulBase

			v := rb.runeAt(i) // also used to compare to jamoT

			switch {

			case jamoLBase <= l && l < jamoLEnd &&

				jamoVBase <= v && v < jamoVEnd:

				// 11xx plus 116x to LV

				rb.assignRune(s, hangulBase+

					(l-jamoLBase)*jamoVTCount+(v-jamoVBase)*jamoTCount)

			case hangulBase <= l && l < hangulEnd &&

				jamoTBase < v && v < jamoTEnd &&

				((l-hangulBase)%jamoTCount) == 0:

				// ACxx plus 11Ax to LVT

				rb.assignRune(s, l+v-jamoTBase)

			default:

				b[k] = b[i]

				k++

			}

		}

	}

	rb.nrune = k

}

// compose recombines the runes in the buffer.

// It should only be used to recompose a single segment, as it will not

// handle alternations between Hangul and non-Hangul characters correctly.

func (rb *reorderBuffer) compose() {

	// Lazily load the map used by the combine func below, but do

	// it outside of the loop.

	recompMapOnce.Do(buildRecompMap)

	// UAX #15, section X5 , including Corrigendum #5

	// "In any character sequence beginning with starter S, a character C is

	//  blocked from S if and only if there is some character B between S

	//  and C, and either B is a starter or it has the same or higher

	//  combining class as C."

	bn := rb.nrune

	if bn == 0 {

		return

	}

	k := 1

	b := rb.rune[:]

	for s, i := 0, 1; i < bn; i++ {

		if isJamoVT(rb.bytesAt(i)) {

			// Redo from start in Hangul mode. Necessary to support

			// U+320E..U+321E in NFKC mode.

			rb.combineHangul(s, i, k)

			return

		}

		ii := b[i]

		// We can only use combineForward as a filter if we later

		// get the info for the combined character. This is more

		// expensive than using the filter. Using combinesBackward()

		// is safe.

		if ii.combinesBackward() {

			cccB := b[k-1].ccc

			cccC := ii.ccc

			blocked := false // b[i] blocked by starter or greater or equal CCC?

			if cccB == 0 {

				s = k - 1

			} else {

				blocked = s != k-1 && cccB >= cccC

			}

			if !blocked {

				combined := combine(rb.runeAt(s), rb.runeAt(i))

				if combined != 0 {

					rb.assignRune(s, combined)

					continue

				}

			}

		}

		b[k] = b[i]

		k++

	}

	rb.nrune = k

}