unicode/bidi/bracket.go - text - Git at Google

 // Copyright 2015 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 bidi

 import (
 	"container/list"
 	"fmt"
 	"sort"
 )

 // This file contains a port of the reference implementation of the
 // Bidi Parentheses Algorithm:
 // http://www.unicode.org/Public/PROGRAMS/BidiReferenceJava/BidiPBAReference.java
 //
 // The implementation in this file covers definitions BD14-BD16 and rule N0
 // of UAX#9.
 //
 // Some preprocessing is done for each rune before data is passed to this
 // algorithm:
 //  - opening and closing brackets are identified
 //  - a bracket pair type, like '(' and ')' is assigned a unique identifier that
 //    is identical for the opening and closing bracket. It is left to do these
 //    mappings.
 //  - The BPA algorithm requires that bracket characters that are canonical
 //    equivalents of each other be able to be substituted for each other.
 //    It is the responsibility of the caller to do this canonicalization.
 //
 // In implementing BD16, this implementation departs slightly from the "logical"
 // algorithm defined in UAX#9. In particular, the stack referenced there
 // supports operations that go beyond a "basic" stack. An equivalent
 // implementation based on a linked list is used here.

 // Bidi_Paired_Bracket_Type
 // BD14. An opening paired bracket is a character whose
 // Bidi_Paired_Bracket_Type property value is Open.
 //
 // BD15. A closing paired bracket is a character whose
 // Bidi_Paired_Bracket_Type property value is Close.
 type bracketType byte

 const (
 	bpNone bracketType = iota
 	bpOpen
 	bpClose
 )

 // bracketPair holds a pair of index values for opening and closing bracket
 // location of a bracket pair.
 type bracketPair struct {
 	opener int
 	closer int
 }

 func (b *bracketPair) String() string {
 	return fmt.Sprintf("(%v, %v)", b.opener, b.closer)
 }

 // bracketPairs is a slice of bracketPairs with a sort.Interface implementation.
 type bracketPairs []bracketPair

 func (b bracketPairs) Len() int           { return len(b) }
 func (b bracketPairs) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }
 func (b bracketPairs) Less(i, j int) bool { return b[i].opener < b[j].opener }

 // resolvePairedBrackets runs the paired bracket part of the UBA algorithm.
 //
 // For each rune, it takes the indexes into the original string, the class the
 // bracket type (in pairTypes) and the bracket identifier (pairValues). It also
 // takes the direction type for the start-of-sentence and the embedding level.
 //
 // The identifiers for bracket types are the rune of the canonicalized opening
 // bracket for brackets (open or close) or 0 for runes that are not brackets.
 func resolvePairedBrackets(s *isolatingRunSequence) {
 	p := bracketPairer{
 		sos:              s.sos,
 		openers:          list.New(),
 		codesIsolatedRun: s.types,
 		indexes:          s.indexes,
 	}
 	dirEmbed := L
 	if s.level&1 != 0 {
 		dirEmbed = R
 	}
 	p.locateBrackets(s.p.pairTypes, s.p.pairValues)
 	p.resolveBrackets(dirEmbed, s.p.initialTypes)
 }

 type bracketPairer struct {
 	sos Class // direction corresponding to start of sequence

 	// The following is a restatement of BD 16 using non-algorithmic language.
 	//
 	// A bracket pair is a pair of characters consisting of an opening
 	// paired bracket and a closing paired bracket such that the
 	// Bidi_Paired_Bracket property value of the former equals the latter,
 	// subject to the following constraints.
 	// - both characters of a pair occur in the same isolating run sequence
 	// - the closing character of a pair follows the opening character
 	// - any bracket character can belong at most to one pair, the earliest possible one
 	// - any bracket character not part of a pair is treated like an ordinary character
 	// - pairs may nest properly, but their spans may not overlap otherwise

 	// Bracket characters with canonical decompositions are supposed to be
 	// treated as if they had been normalized, to allow normalized and non-
 	// normalized text to give the same result. In this implementation that step
 	// is pushed out to the caller. The caller has to ensure that the pairValue
 	// slices contain the rune of the opening bracket after normalization for
 	// any opening or closing bracket.

 	openers *list.List // list of positions for opening brackets

 	// bracket pair positions sorted by location of opening bracket
 	pairPositions bracketPairs

 	codesIsolatedRun []Class // directional bidi codes for an isolated run
 	indexes          []int   // array of index values into the original string

 }

 // matchOpener reports whether characters at given positions form a matching
 // bracket pair.
 func (p *bracketPairer) matchOpener(pairValues []rune, opener, closer int) bool {
 	return pairValues[p.indexes[opener]] == pairValues[p.indexes[closer]]
 }

 const maxPairingDepth = 63

 // locateBrackets locates matching bracket pairs according to BD16.
 //
 // This implementation uses a linked list instead of a stack, because, while
 // elements are added at the front (like a push) they are not generally removed
 // in atomic 'pop' operations, reducing the benefit of the stack archetype.
 func (p *bracketPairer) locateBrackets(pairTypes []bracketType, pairValues []rune) {
 	// traverse the run
 	// do that explicitly (not in a for-each) so we can record position
 	for i, index := range p.indexes {

 		// look at the bracket type for each character
 		if pairTypes[index] == bpNone || p.codesIsolatedRun[i] != ON {
 			// continue scanning
 			continue
 		}
 		switch pairTypes[index] {
 		case bpOpen:
 			// check if maximum pairing depth reached
 			if p.openers.Len() == maxPairingDepth {
 				p.openers.Init()
 				return
 			}
 			// remember opener location, most recent first
 			p.openers.PushFront(i)

 		case bpClose:
 			// see if there is a match
 			count := 0
 			for elem := p.openers.Front(); elem != nil; elem = elem.Next() {
 				count++
 				opener := elem.Value.(int)
 				if p.matchOpener(pairValues, opener, i) {
 					// if the opener matches, add nested pair to the ordered list
 					p.pairPositions = append(p.pairPositions, bracketPair{opener, i})
 					// remove up to and including matched opener
 					for ; count > 0; count-- {
 						p.openers.Remove(p.openers.Front())
 					}
 					break
 				}
 			}
 			sort.Sort(p.pairPositions)
 			// if we get here, the closing bracket matched no openers
 			// and gets ignored
 		}
 	}
 }

 // Bracket pairs within an isolating run sequence are processed as units so
 // that both the opening and the closing paired bracket in a pair resolve to
 // the same direction.
 //
 // N0. Process bracket pairs in an isolating run sequence sequentially in
 // the logical order of the text positions of the opening paired brackets
 // using the logic given below. Within this scope, bidirectional types EN
 // and AN are treated as R.
 //
 // Identify the bracket pairs in the current isolating run sequence
 // according to BD16. For each bracket-pair element in the list of pairs of
 // text positions:
 //
 // a Inspect the bidirectional types of the characters enclosed within the
 // bracket pair.
 //
 // b If any strong type (either L or R) matching the embedding direction is
 // found, set the type for both brackets in the pair to match the embedding
 // direction.
 //
 // o [ e ] o -> o e e e o
 //
 // o [ o e ] -> o e o e e
 //
 // o [ NI e ] -> o e NI e e
 //
 // c Otherwise, if a strong type (opposite the embedding direction) is
 // found, test for adjacent strong types as follows: 1 First, check
 // backwards before the opening paired bracket until the first strong type
 // (L, R, or sos) is found. If that first preceding strong type is opposite
 // the embedding direction, then set the type for both brackets in the pair
 // to that type. 2 Otherwise, set the type for both brackets in the pair to
 // the embedding direction.
 //
 // o [ o ] e -> o o o o e
 //
 // o [ o NI ] o -> o o o NI o o
 //
 // e [ o ] o -> e e o e o
 //
 // e [ o ] e -> e e o e e
 //
 // e ( o [ o ] NI ) e -> e e o o o o NI e e
 //
 // d Otherwise, do not set the type for the current bracket pair. Note that
 // if the enclosed text contains no strong types the paired brackets will
 // both resolve to the same level when resolved individually using rules N1
 // and N2.
 //
 // e ( NI ) o -> e ( NI ) o

 // getStrongTypeN0 maps character's directional code to strong type as required
 // by rule N0.
 //
 // TODO: have separate type for "strong" directionality.
 func (p *bracketPairer) getStrongTypeN0(index int) Class {
 	switch p.codesIsolatedRun[index] {
 	// in the scope of N0, number types are treated as R
 	case EN, AN, AL, R:
 		return R
 	case L:
 		return L
 	default:
 		return ON
 	}
 }

 // classifyPairContent reports the strong types contained inside a Bracket Pair,
 // assuming the given embedding direction.
 //
 // It returns ON if no strong type is found. If a single strong type is found,
 // it returns this this type. Otherwise it returns the embedding direction.
 //
 // TODO: use separate type for "strong" directionality.
 func (p *bracketPairer) classifyPairContent(loc bracketPair, dirEmbed Class) Class {
 	dirOpposite := ON
 	for i := loc.opener + 1; i < loc.closer; i++ {
 		dir := p.getStrongTypeN0(i)
 		if dir == ON {
 			continue
 		}
 		if dir == dirEmbed {
 			return dir // type matching embedding direction found
 		}
 		dirOpposite = dir
 	}
 	// return ON if no strong type found, or class opposite to dirEmbed
 	return dirOpposite
 }

 // classBeforePair determines which strong types are present before a Bracket
 // Pair. Return R or L if strong type found, otherwise ON.
 func (p *bracketPairer) classBeforePair(loc bracketPair) Class {
 	for i := loc.opener - 1; i >= 0; i-- {
 		if dir := p.getStrongTypeN0(i); dir != ON {
 			return dir
 		}
 	}
 	// no strong types found, return sos
 	return p.sos
 }

 // assignBracketType implements rule N0 for a single bracket pair.
 func (p *bracketPairer) assignBracketType(loc bracketPair, dirEmbed Class, initialTypes []Class) {
 	// rule "N0, a", inspect contents of pair
 	dirPair := p.classifyPairContent(loc, dirEmbed)

 	// dirPair is now L, R, or N (no strong type found)

 	// the following logical tests are performed out of order compared to
 	// the statement of the rules but yield the same results
 	if dirPair == ON {
 		return // case "d" - nothing to do
 	}

 	if dirPair != dirEmbed {
 		// case "c": strong type found, opposite - check before (c.1)
 		dirPair = p.classBeforePair(loc)
 		if dirPair == dirEmbed || dirPair == ON {
 			// no strong opposite type found before - use embedding (c.2)
 			dirPair = dirEmbed
 		}
 	}
 	// else: case "b", strong type found matching embedding,
 	// no explicit action needed, as dirPair is already set to embedding
 	// direction

 	// set the bracket types to the type found
 	p.setBracketsToType(loc, dirPair, initialTypes)
 }

 func (p *bracketPairer) setBracketsToType(loc bracketPair, dirPair Class, initialTypes []Class) {
 	p.codesIsolatedRun[loc.opener] = dirPair
 	p.codesIsolatedRun[loc.closer] = dirPair

 	for i := loc.opener + 1; i < loc.closer; i++ {
 		index := p.indexes[i]
 		if initialTypes[index] != NSM {
 			break
 		}
 		p.codesIsolatedRun[i] = dirPair
 	}

 	for i := loc.closer + 1; i < len(p.indexes); i++ {
 		index := p.indexes[i]
 		if initialTypes[index] != NSM {
 			break
 		}
 		p.codesIsolatedRun[i] = dirPair
 	}
 }

 // resolveBrackets implements rule N0 for a list of pairs.
 func (p *bracketPairer) resolveBrackets(dirEmbed Class, initialTypes []Class) {
 	for _, loc := range p.pairPositions {
 		p.assignBracketType(loc, dirEmbed, initialTypes)
 	}
 }
	// Copyright 2015 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 bidi

	import (
	"container/list"
	"fmt"
	"sort"
	)

	// This file contains a port of the reference implementation of the
	// Bidi Parentheses Algorithm:
	// http://www.unicode.org/Public/PROGRAMS/BidiReferenceJava/BidiPBAReference.java
	//
	// The implementation in this file covers definitions BD14-BD16 and rule N0
	// of UAX#9.
	//
	// Some preprocessing is done for each rune before data is passed to this
	// algorithm:
	// - opening and closing brackets are identified
	// - a bracket pair type, like '(' and ')' is assigned a unique identifier that
	// is identical for the opening and closing bracket. It is left to do these
	// mappings.
	// - The BPA algorithm requires that bracket characters that are canonical
	// equivalents of each other be able to be substituted for each other.
	// It is the responsibility of the caller to do this canonicalization.
	//
	// In implementing BD16, this implementation departs slightly from the "logical"
	// algorithm defined in UAX#9. In particular, the stack referenced there
	// supports operations that go beyond a "basic" stack. An equivalent
	// implementation based on a linked list is used here.

	// Bidi_Paired_Bracket_Type
	// BD14. An opening paired bracket is a character whose
	// Bidi_Paired_Bracket_Type property value is Open.
	//
	// BD15. A closing paired bracket is a character whose
	// Bidi_Paired_Bracket_Type property value is Close.
	type bracketType byte

	const (
	bpNone bracketType = iota
	bpOpen
	bpClose
	)

	// bracketPair holds a pair of index values for opening and closing bracket
	// location of a bracket pair.
	type bracketPair struct {
	opener int
	closer int
	}

	func (b *bracketPair) String() string {
	return fmt.Sprintf("(%v, %v)", b.opener, b.closer)
	}

	// bracketPairs is a slice of bracketPairs with a sort.Interface implementation.
	type bracketPairs []bracketPair

	func (b bracketPairs) Len() int { return len(b) }
	func (b bracketPairs) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
	func (b bracketPairs) Less(i, j int) bool { return b[i].opener < b[j].opener }

	// resolvePairedBrackets runs the paired bracket part of the UBA algorithm.
	//
	// For each rune, it takes the indexes into the original string, the class the
	// bracket type (in pairTypes) and the bracket identifier (pairValues). It also
	// takes the direction type for the start-of-sentence and the embedding level.
	//
	// The identifiers for bracket types are the rune of the canonicalized opening
	// bracket for brackets (open or close) or 0 for runes that are not brackets.
	func resolvePairedBrackets(s *isolatingRunSequence) {
	p := bracketPairer{
	sos: s.sos,
	openers: list.New(),
	codesIsolatedRun: s.types,
	indexes: s.indexes,
	}
	dirEmbed := L
	if s.level&1 != 0 {
	dirEmbed = R
	}
	p.locateBrackets(s.p.pairTypes, s.p.pairValues)
	p.resolveBrackets(dirEmbed, s.p.initialTypes)
	}

	type bracketPairer struct {
	sos Class // direction corresponding to start of sequence

	// The following is a restatement of BD 16 using non-algorithmic language.
	//
	// A bracket pair is a pair of characters consisting of an opening
	// paired bracket and a closing paired bracket such that the
	// Bidi_Paired_Bracket property value of the former equals the latter,
	// subject to the following constraints.
	// - both characters of a pair occur in the same isolating run sequence
	// - the closing character of a pair follows the opening character
	// - any bracket character can belong at most to one pair, the earliest possible one
	// - any bracket character not part of a pair is treated like an ordinary character
	// - pairs may nest properly, but their spans may not overlap otherwise

	// Bracket characters with canonical decompositions are supposed to be
	// treated as if they had been normalized, to allow normalized and non-
	// normalized text to give the same result. In this implementation that step
	// is pushed out to the caller. The caller has to ensure that the pairValue
	// slices contain the rune of the opening bracket after normalization for
	// any opening or closing bracket.

	openers *list.List // list of positions for opening brackets

	// bracket pair positions sorted by location of opening bracket
	pairPositions bracketPairs

	codesIsolatedRun []Class // directional bidi codes for an isolated run
	indexes []int // array of index values into the original string

	}

	// matchOpener reports whether characters at given positions form a matching
	// bracket pair.
	func (p *bracketPairer) matchOpener(pairValues []rune, opener, closer int) bool {
	return pairValues[p.indexes[opener]] == pairValues[p.indexes[closer]]
	}

	const maxPairingDepth = 63

	// locateBrackets locates matching bracket pairs according to BD16.
	//
	// This implementation uses a linked list instead of a stack, because, while
	// elements are added at the front (like a push) they are not generally removed
	// in atomic 'pop' operations, reducing the benefit of the stack archetype.
	func (p *bracketPairer) locateBrackets(pairTypes []bracketType, pairValues []rune) {
	// traverse the run
	// do that explicitly (not in a for-each) so we can record position
	for i, index := range p.indexes {

	// look at the bracket type for each character
	if pairTypes[index] == bpNone \|\| p.codesIsolatedRun[i] != ON {
	// continue scanning
	continue
	}
	switch pairTypes[index] {
	case bpOpen:
	// check if maximum pairing depth reached
	if p.openers.Len() == maxPairingDepth {
	p.openers.Init()
	return
	}
	// remember opener location, most recent first
	p.openers.PushFront(i)

	case bpClose:
	// see if there is a match
	count := 0
	for elem := p.openers.Front(); elem != nil; elem = elem.Next() {
	count++
	opener := elem.Value.(int)
	if p.matchOpener(pairValues, opener, i) {
	// if the opener matches, add nested pair to the ordered list
	p.pairPositions = append(p.pairPositions, bracketPair{opener, i})
	// remove up to and including matched opener
	for ; count > 0; count-- {
	p.openers.Remove(p.openers.Front())
	}
	break
	}
	}
	sort.Sort(p.pairPositions)
	// if we get here, the closing bracket matched no openers
	// and gets ignored
	}
	}
	}

	// Bracket pairs within an isolating run sequence are processed as units so
	// that both the opening and the closing paired bracket in a pair resolve to
	// the same direction.
	//
	// N0. Process bracket pairs in an isolating run sequence sequentially in
	// the logical order of the text positions of the opening paired brackets
	// using the logic given below. Within this scope, bidirectional types EN
	// and AN are treated as R.
	//
	// Identify the bracket pairs in the current isolating run sequence
	// according to BD16. For each bracket-pair element in the list of pairs of
	// text positions:
	//
	// a Inspect the bidirectional types of the characters enclosed within the
	// bracket pair.
	//
	// b If any strong type (either L or R) matching the embedding direction is
	// found, set the type for both brackets in the pair to match the embedding
	// direction.
	//
	// o [ e ] o -> o e e e o
	//
	// o [ o e ] -> o e o e e
	//
	// o [ NI e ] -> o e NI e e
	//
	// c Otherwise, if a strong type (opposite the embedding direction) is
	// found, test for adjacent strong types as follows: 1 First, check
	// backwards before the opening paired bracket until the first strong type
	// (L, R, or sos) is found. If that first preceding strong type is opposite
	// the embedding direction, then set the type for both brackets in the pair
	// to that type. 2 Otherwise, set the type for both brackets in the pair to
	// the embedding direction.
	//
	// o [ o ] e -> o o o o e
	//
	// o [ o NI ] o -> o o o NI o o
	//
	// e [ o ] o -> e e o e o
	//
	// e [ o ] e -> e e o e e
	//
	// e ( o [ o ] NI ) e -> e e o o o o NI e e
	//
	// d Otherwise, do not set the type for the current bracket pair. Note that
	// if the enclosed text contains no strong types the paired brackets will
	// both resolve to the same level when resolved individually using rules N1
	// and N2.
	//
	// e ( NI ) o -> e ( NI ) o

	// getStrongTypeN0 maps character's directional code to strong type as required
	// by rule N0.
	//
	// TODO: have separate type for "strong" directionality.
	func (p *bracketPairer) getStrongTypeN0(index int) Class {
	switch p.codesIsolatedRun[index] {
	// in the scope of N0, number types are treated as R
	case EN, AN, AL, R:
	return R
	case L:
	return L
	default:
	return ON
	}
	}

	// classifyPairContent reports the strong types contained inside a Bracket Pair,
	// assuming the given embedding direction.
	//
	// It returns ON if no strong type is found. If a single strong type is found,
	// it returns this this type. Otherwise it returns the embedding direction.
	//
	// TODO: use separate type for "strong" directionality.
	func (p *bracketPairer) classifyPairContent(loc bracketPair, dirEmbed Class) Class {
	dirOpposite := ON
	for i := loc.opener + 1; i < loc.closer; i++ {
	dir := p.getStrongTypeN0(i)
	if dir == ON {
	continue
	}
	if dir == dirEmbed {
	return dir // type matching embedding direction found
	}
	dirOpposite = dir
	}
	// return ON if no strong type found, or class opposite to dirEmbed
	return dirOpposite
	}

	// classBeforePair determines which strong types are present before a Bracket
	// Pair. Return R or L if strong type found, otherwise ON.
	func (p *bracketPairer) classBeforePair(loc bracketPair) Class {
	for i := loc.opener - 1; i >= 0; i-- {
	if dir := p.getStrongTypeN0(i); dir != ON {
	return dir
	}
	}
	// no strong types found, return sos
	return p.sos
	}

	// assignBracketType implements rule N0 for a single bracket pair.
	func (p *bracketPairer) assignBracketType(loc bracketPair, dirEmbed Class, initialTypes []Class) {
	// rule "N0, a", inspect contents of pair
	dirPair := p.classifyPairContent(loc, dirEmbed)

	// dirPair is now L, R, or N (no strong type found)

	// the following logical tests are performed out of order compared to
	// the statement of the rules but yield the same results
	if dirPair == ON {
	return // case "d" - nothing to do
	}

	if dirPair != dirEmbed {
	// case "c": strong type found, opposite - check before (c.1)
	dirPair = p.classBeforePair(loc)
	if dirPair == dirEmbed \|\| dirPair == ON {
	// no strong opposite type found before - use embedding (c.2)
	dirPair = dirEmbed
	}
	}
	// else: case "b", strong type found matching embedding,
	// no explicit action needed, as dirPair is already set to embedding
	// direction

	// set the bracket types to the type found
	p.setBracketsToType(loc, dirPair, initialTypes)
	}

	func (p *bracketPairer) setBracketsToType(loc bracketPair, dirPair Class, initialTypes []Class) {
	p.codesIsolatedRun[loc.opener] = dirPair
	p.codesIsolatedRun[loc.closer] = dirPair

	for i := loc.opener + 1; i < loc.closer; i++ {
	index := p.indexes[i]
	if initialTypes[index] != NSM {
	break
	}
	p.codesIsolatedRun[i] = dirPair
	}

	for i := loc.closer + 1; i < len(p.indexes); i++ {
	index := p.indexes[i]
	if initialTypes[index] != NSM {
	break
	}
	p.codesIsolatedRun[i] = dirPair
	}
	}

	// resolveBrackets implements rule N0 for a list of pairs.
	func (p *bracketPairer) resolveBrackets(dirEmbed Class, initialTypes []Class) {
	for _, loc := range p.pairPositions {
	p.assignBracketType(loc, dirEmbed, initialTypes)
	}
	}