aboutsummaryrefslogtreecommitdiffstats
path: root/vendor/golang.org/x/text/unicode/bidi/bracket.go
blob: 18539397914bfb0dfe473d0b9f3e55189d35f8b4 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
// 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:
// https://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 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)
	}
}