-
Notifications
You must be signed in to change notification settings - Fork 226
Expand file tree
/
Copy pathIntegerFormatter.java
More file actions
782 lines (705 loc) · 27.3 KB
/
IntegerFormatter.java
File metadata and controls
782 lines (705 loc) · 27.3 KB
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
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
// Copyright (c) Jython Developers
package org.python.core.stringlib;
import java.math.BigInteger;
import org.python.core.Py;
import org.python.core.PyInteger;
import org.python.core.PyLong;
import org.python.core.PyObject;
import org.python.core.PyString;
import org.python.core.PySystemState;
import org.python.core.stringlib.InternalFormat.Spec;
/**
* A class that provides the implementation of integer formatting. In a limited way, it acts like a
* StringBuilder to which text and one or more numbers may be appended, formatted according to the
* format specifier supplied at construction. These are ephemeral objects that are not, on their
* own, thread safe.
*/
public class IntegerFormatter extends InternalFormat.Formatter {
/**
* Construct the formatter from a client-supplied buffer, to which the result will be appended,
* and a specification. Sets {@link #mark} to the end of the buffer.
*
* @param result destination buffer
* @param spec parsed conversion specification
*/
public IntegerFormatter(StringBuilder result, Spec spec) {
super(result, spec);
}
/**
* Construct the formatter from a specification, allocating a buffer internally for the result.
*
* @param spec parsed conversion specification
*/
public IntegerFormatter(Spec spec) {
// Rule of thumb: big enough for 32-bit binary with base indicator 0b
this(new StringBuilder(34), spec);
}
/*
* Re-implement the text appends so they return the right type.
*/
@Override
public IntegerFormatter append(char c) {
super.append(c);
return this;
}
@Override
public IntegerFormatter append(CharSequence csq) {
super.append(csq);
return this;
}
@Override
public IntegerFormatter append(CharSequence csq, int start, int end) //
throws IndexOutOfBoundsException {
super.append(csq, start, end);
return this;
}
/**
* Format a {@link BigInteger}, which is the implementation type of Jython <code>long</code>,
* according to the specification represented by this <code>IntegerFormatter</code>. The
* conversion type, and flags for grouping or base prefix are dealt with here. At the point this
* is used, we know the {@link #spec} is one of the integer types.
*
* @param value to convert
* @return this object
*/
@SuppressWarnings("fallthrough")
public IntegerFormatter format(BigInteger value) {
try {
// Different process for each format type.
switch (spec.type) {
case 'd':
case Spec.NONE:
case 'u':
case 'i':
// None format or d-format: decimal
format_d(value);
break;
case 'x':
// hexadecimal.
format_x(value, false);
break;
case 'X':
// HEXADECIMAL!
format_x(value, true);
break;
case 'o':
// Octal.
format_o(value);
break;
case 'b':
// Binary.
format_b(value);
break;
case 'c':
// Binary.
format_c(value);
break;
case 'n':
// Locale-sensitive version of d-format should be here.
format_d(value);
break;
default:
// Should never get here, since this was checked in caller.
throw unknownFormat(spec.type, "long");
}
// If required to, group the whole-part digits.
if (spec.grouping) {
groupDigits(3, ',');
}
return this;
} catch (OutOfMemoryError eme) {
// Most probably due to excessive precision.
throw precisionTooLarge("long");
}
}
/**
* Format the value as decimal (into {@link #result}). The option for mandatory sign is dealt
* with by reference to the format specification.
*
* @param value to convert
*/
void format_d(BigInteger value) {
String number;
if (value.signum() < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(null);
number = value.negate().toString();
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(null);
number = value.toString();
}
appendNumber(number);
}
/**
* Format the value as hexadecimal (into {@link #result}), with the option of using upper-case
* or lower-case letters. The options for mandatory sign and for the presence of a base-prefix
* "0x" or "0X" are dealt with by reference to the format specification.
*
* @param value to convert
* @param upper if the hexadecimal should be upper case
*/
void format_x(BigInteger value, boolean upper) {
String base = upper ? "0X" : "0x";
String number;
if (value.signum() < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(base);
number = toHexString(value.negate());
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(base);
number = toHexString(value);
}
// Append to result, case-shifted if necessary.
if (upper) {
number = number.toUpperCase();
}
appendNumber(number);
}
/**
* Format the value as octal (into {@link #result}). The options for mandatory sign and for the
* presence of a base-prefix "0o" are dealt with by reference to the format specification.
*
* @param value to convert
*/
void format_o(BigInteger value) {
String base = "0o";
String number;
if (value.signum() < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(base);
number = toOctalString(value.negate());
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(base);
number = toOctalString(value);
}
// Append to result.
appendNumber(number);
}
/**
* Format the value as binary (into {@link #result}). The options for mandatory sign and for the
* presence of a base-prefix "0b" are dealt with by reference to the format specification.
*
* @param value to convert
*/
void format_b(BigInteger value) {
String base = "0b";
String number;
if (value.signum() < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(base);
number = toBinaryString(value.negate());
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(base);
number = toBinaryString(value);
}
// Append to result.
appendNumber(number);
}
/**
* Format the value as a character (into {@link #result}).
*
* @param value to convert
*/
void format_c(BigInteger value) {
// Limit is 256 if we're formatting for byte output, unicode range otherwise.
BigInteger limit = bytes ? LIMIT_BYTE : LIMIT_UNICODE;
if (value.signum() < 0 || value.compareTo(limit) >= 0) {
throw Py.OverflowError("%c arg not in range(0x" + toHexString(limit) + ")");
} else {
result.appendCodePoint(value.intValue());
}
}
// Limits used in format_c(BigInteger)
private static final BigInteger LIMIT_UNICODE = BigInteger
.valueOf(PySystemState.maxunicode + 1);
private static final BigInteger LIMIT_BYTE = BigInteger.valueOf(256);
/**
* Format an integer according to the specification represented by this
* <code>IntegerFormatter</code>. The conversion type, and flags for grouping or base prefix are
* dealt with here. At the point this is used, we know the {@link #spec} is one of the integer
* types.
*
* @param value to convert
* @return this object
*/
@SuppressWarnings("fallthrough")
public IntegerFormatter format(int value) {
try {
// Scratch all instance variables and start = result.length().
setStart();
// Different process for each format type.
switch (spec.type) {
case 'd':
case Spec.NONE:
case 'u':
case 'i':
// None format or d-format: decimal
format_d(value);
break;
case 'x':
// hexadecimal.
format_x(value, false);
break;
case 'X':
// HEXADECIMAL!
format_x(value, true);
break;
case 'o':
// Octal.
format_o(value);
break;
case 'b':
// Binary.
format_b(value);
break;
case 'c':
case '%':
// Binary.
format_c(value);
break;
case 'n':
// Locale-sensitive version of d-format should be here.
format_d(value);
break;
default:
// Should never get here, since this was checked in caller.
throw unknownFormat(spec.type, "integer");
}
// If required to, group the whole-part digits.
if (spec.grouping) {
groupDigits(3, ',');
}
return this;
} catch (OutOfMemoryError eme) {
// Most probably due to excessive precision.
throw precisionTooLarge("integer");
}
}
/**
* Format the value as decimal (into {@link #result}). The option for mandatory sign is dealt
* with by reference to the format specification.
*
* @param value to convert
*/
void format_d(int value) {
String number;
if (value < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(null);
// Here there is a special case for int min value due to wrapping, to avoid a double
// negative sign being added see http://bugs.jython.org/issue2672
// The string constant here is -Integer.MIN_VALUE
number = value == Integer.MIN_VALUE ? "2147483648" : Integer.toString(-value);
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(null);
number = Integer.toString(value);
}
appendNumber(number);
}
/**
* Format the value as hexadecimal (into {@link #result}), with the option of using upper-case
* or lower-case letters. The options for mandatory sign and for the presence of a base-prefix
* "0x" or "0X" are dealt with by reference to the format specification.
*
* @param value to convert
* @param upper if the hexadecimal should be upper case
*/
void format_x(int value, boolean upper) {
String base = upper ? "0X" : "0x";
String number;
if (value < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(base);
number = Integer.toHexString(-value);
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(base);
number = Integer.toHexString(value);
}
// Append to result, case-shifted if necessary.
if (upper) {
number = number.toUpperCase();
}
appendNumber(number);
}
/**
* Format the value as octal (into {@link #result}). The options for mandatory sign and for the
* presence of a base-prefix "0o" are dealt with by reference to the format specification.
*
* @param value to convert
*/
void format_o(int value) {
String base = "0o";
String number;
if (value < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(base);
number = Integer.toOctalString(-value);
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(base);
number = Integer.toOctalString(value);
}
// Append to result.
appendNumber(number);
}
/**
* Format the value as binary (into {@link #result}). The options for mandatory sign and for the
* presence of a base-prefix "0b" are dealt with by reference to the format specification.
*
* @param value to convert
*/
void format_b(int value) {
String base = "0b";
String number;
if (value < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(base);
number = Integer.toBinaryString(-value);
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(base);
number = Integer.toBinaryString(value);
}
// Append to result.
appendNumber(number);
}
/**
* Format the value as a character (into {@link #result}).
*
* @param value to convert
*/
void format_c(int value) {
// Limit is 256 if we're formatting for byte output, unicode range otherwise.
int limit = bytes ? 256 : PySystemState.maxunicode + 1;
if (value < 0 || value >= limit) {
throw Py.OverflowError("%c arg not in range(0x" + Integer.toHexString(limit) + ")");
} else {
result.appendCodePoint(value);
}
}
/**
* Append to {@link #result} buffer a sign (if one is specified for positive numbers) and, in
* alternate mode, the base marker provided. The sign and base marker are together considered to
* be the "sign" of the converted number, spanned by {@link #lenSign}. This is relevant when we
* come to insert padding.
*
* @param base marker "0x" or "0X" for hex, "0o" for octal, "0b" for binary, "" or
* <code>null</code> for decimal.
*/
final void positiveSign(String base) {
// Does the format specify a sign for positive values?
char sign = spec.sign;
if (Spec.specified(sign) && sign != '-') {
append(sign);
lenSign = 1;
}
// Does the format call for a base prefix?
if (base != null && spec.alternate) {
append(base);
lenSign += base.length();
}
}
/**
* Append to {@link #result} buffer a minus sign and, in alternate mode, the base marker
* provided. The sign and base marker are together considered to be the "sign" of the converted
* number, spanned by {@link #lenSign}. This is relevant when we come to insert padding.
*
* @param base marker ("0x" or "0X" for hex, "0" for octal, <code>null</code> or "" for decimal.
*/
final void negativeSign(String base) {
// Insert a minus sign unconditionally.
append('-');
lenSign = 1;
// Does the format call for a base prefix?
if (base != null && spec.alternate) {
append(base);
lenSign += base.length();
}
}
/**
* Append a string (number) to {@link #result} and set {@link #lenWhole} to its length .
*
* @param number to append
*/
void appendNumber(String number) {
lenWhole = number.length();
append(number);
}
// For hex-conversion by lookup
private static final String LOOKUP = "0123456789abcdef";
/**
* A more efficient algorithm for generating a hexadecimal representation of a byte array.
* {@link BigInteger#toString(int)} is too slow because it generalizes to any radix and,
* consequently, is implemented using expensive mathematical operations.
*
* @param value the value to generate a hexadecimal string from
* @return the hexadecimal representation of value, with "-" sign prepended if necessary
*/
private static final String toHexString(BigInteger value) {
int signum = value.signum();
// obvious shortcut
if (signum == 0) {
return "0";
}
// we want to work in absolute numeric value (negative sign is added afterward)
byte[] input = value.abs().toByteArray();
StringBuilder sb = new StringBuilder(input.length * 2);
int b;
for (int i = 0; i < input.length; i++) {
b = input[i] & 0xFF;
sb.append(LOOKUP.charAt(b >> 4));
sb.append(LOOKUP.charAt(b & 0x0F));
}
// before returning the char array as string, remove leading zeroes, but not the last one
String result = sb.toString().replaceFirst("^0+(?!$)", "");
return signum < 0 ? "-" + result : result;
}
/**
* A more efficient algorithm for generating an octal representation of a byte array.
* {@link BigInteger#toString(int)} is too slow because it generalizes to any radix and,
* consequently, is implemented using expensive mathematical operations.
*
* @param value the value to generate an octal string from
* @return the octal representation of value, with "-" sign prepended if necessary
*/
private static final String toOctalString(BigInteger value) {
int signum = value.signum();
// obvious shortcut
if (signum == 0) {
return "0";
}
byte[] input = value.abs().toByteArray();
if (input.length < 3) {
return value.toString(8);
}
StringBuilder sb = new StringBuilder(input.length * 3);
// working backwards, three bytes at a time
int threebytes;
int trip1, trip2, trip3; // most, middle, and least significant bytes in the triplet
for (int i = input.length - 1; i >= 0; i -= 3) {
trip3 = input[i] & 0xFF;
trip2 = ((i - 1) >= 0) ? (input[i - 1] & 0xFF) : 0x00;
trip1 = ((i - 2) >= 0) ? (input[i - 2] & 0xFF) : 0x00;
threebytes = trip3 | (trip2 << 8) | (trip1 << 16);
// convert the three-byte value into an eight-character octal string
for (int j = 0; j < 8; j++) {
sb.append(LOOKUP.charAt((threebytes >> (j * 3)) & 0x000007));
}
}
String result = sb.reverse().toString().replaceFirst("^0+(?!%)", "");
return signum < 0 ? "-" + result : result;
}
/**
* A more efficient algorithm for generating a binary representation of a byte array.
* {@link BigInteger#toString(int)} is too slow because it generalizes to any radix and,
* consequently, is implemented using expensive mathematical operations.
*
* @param value the value to generate a binary string from
* @return the binary representation of value, with "-" sign prepended if necessary
*/
private static final String toBinaryString(BigInteger value) {
int signum = value.signum();
// obvious shortcut
if (signum == 0) {
return "0";
}
// we want to work in absolute numeric value (negative sign is added afterward)
byte[] input = value.abs().toByteArray();
StringBuilder sb = new StringBuilder(value.bitCount());
int b;
for (int i = 0; i < input.length; i++) {
b = input[i] & 0xFF;
for (int bit = 7; bit >= 0; bit--) {
sb.append(((b >> bit) & 0x1) > 0 ? "1" : "0");
}
}
// before returning the char array as string, remove leading zeroes, but not the last one
String result = sb.toString().replaceFirst("^0+(?!$)", "");
return signum < 0 ? "-" + result : result;
}
/** Format specification used by bin(). */
public static final Spec BIN = InternalFormat.fromText("#b");
/** Format specification used by oct(). */
public static final Spec OCT = InternalFormat.fromText("#o");
/** Format specification used by hex(). */
public static final Spec HEX = InternalFormat.fromText("#x");
/**
* Convert the object to binary according to the conventions of Python built-in
* <code>bin()</code>. The object's __index__ method is called, and is responsible for raising
* the appropriate error (which the base {@link PyObject#__index__()} does).
*
* @param number to convert
* @return PyString converted result
*/
// Follow this pattern in Python 3, where objects no longer have __hex__, __oct__ members.
public static PyString bin(PyObject number) {
return formatNumber(number, BIN);
}
/**
* Convert the object according to the conventions of Python built-in <code>hex()</code>, or
* <code>oct()</code>. The object's <code>__index__</code> method is called, and is responsible
* for raising the appropriate error (which the base {@link PyObject#__index__()} does).
*
* @param number to convert
* @return PyString converted result
*/
public static PyString formatNumber(PyObject number, Spec spec) {
number = number.__index__();
IntegerFormatter f = new IntegerFormatter(spec);
if (number instanceof PyInteger) {
f.format(((PyInteger)number).getValue());
} else {
f.format(((PyLong)number).getValue());
}
return new PyString(f.getResult());
}
/**
* A minor variation on {@link IntegerFormatter} to handle "traditional" %-formatting. The
* difference is in support for <code>spec.precision</code>, the formatting octal in "alternate"
* mode (0 and 0123, not 0o0 and 0o123), and in c-format (in the error logic).
*/
public static class Traditional extends IntegerFormatter {
/**
* Construct the formatter from a client-supplied buffer, to which the result will be
* appended, and a specification. Sets {@link #mark} to the end of the buffer.
*
* @param result destination buffer
* @param spec parsed conversion specification
*/
public Traditional(StringBuilder result, Spec spec) {
super(result, spec);
}
/**
* Construct the formatter from a specification, allocating a buffer internally for the
* result.
*
* @param spec parsed conversion specification
*/
public Traditional(Spec spec) {
this(new StringBuilder(), spec);
}
/**
* Format the value as octal (into {@link #result}). The options for mandatory sign and for
* the presence of a base-prefix "0" are dealt with by reference to the format
* specification.
*
* @param value to convert
*/
@Override
void format_o(BigInteger value) {
String number;
int signum = value.signum();
if (signum < 0) {
// Negative value: deal with sign and base, and convert magnitude.
negativeSign(null);
number = toOctalString(value.negate());
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(null);
number = toOctalString(value);
}
// Append to result.
appendOctalNumber(number);
}
/**
* Format the value as a character (into {@link #result}).
*
* @param value to convert
*/
@Override
void format_c(BigInteger value) {
if (value.signum() < 0) {
throw Py.OverflowError("unsigned byte integer is less than minimum");
} else {
// Limit is 256 if we're formatting for byte output, unicode range otherwise.
BigInteger limit = bytes ? LIMIT_BYTE : LIMIT_UNICODE;
if (value.compareTo(limit) >= 0) {
throw Py.OverflowError("unsigned byte integer is greater than maximum");
} else {
result.appendCodePoint(value.intValue());
}
}
}
/**
* Format the value as octal (into {@link #result}). The options for mandatory sign and for
* the presence of a base-prefix "0" are dealt with by reference to the format
* specification.
*
* @param value to convert
*/
@Override
void format_o(int value) {
String number;
if (value < 0) {
// Negative value: deal with sign and convert magnitude.
negativeSign(null);
number = Integer.toOctalString(-value);
} else {
// Positive value: deal with sign, base and magnitude.
positiveSign(null);
number = Integer.toOctalString(value);
}
// Append to result.
appendOctalNumber(number);
}
/**
* Format the value as a character (into {@link #result}).
*
* @param value to convert
*/
@Override
void format_c(int value) {
if (value < 0) {
throw Py.OverflowError("unsigned byte integer is less than minimum");
} else {
// Limit is 256 if we're formatting for byte output, unicode range otherwise.
int limit = bytes ? 256 : PySystemState.maxunicode + 1;
if (value >= limit) {
throw Py.OverflowError("unsigned byte integer is greater than maximum");
} else {
result.appendCodePoint(value);
}
}
}
/**
* Append a string (number) to {@link #result}, but insert leading zeros first in order
* that, on return, the whole-part length #lenWhole should be no less than the precision.
*
* @param number to append
*/
@Override
void appendNumber(String number) {
int n, p = spec.getPrecision(0);
for (n = number.length(); n < p; n++) {
result.append('0');
}
lenWhole = n;
append(number);
}
/**
* Append a string (number) to {@link #result}, but insert leading zeros first in order
* that, on return, the whole-part length #lenWhole should be no less than the precision.
* Octal numbers must begin with a zero if <code>spec.alternate==true</code>, so if the
* number passed in does not start with a zero, at least one will be inserted.
*
* @param number to append
*/
void appendOctalNumber(String number) {
int n = number.length(), p = spec.getPrecision(0);
if (spec.alternate && number.charAt(0) != '0' && n >= p) {
p = n + 1;
}
for (; n < p; n++) {
result.append('0');
}
lenWhole = n;
append(number);
}
}
}