nitlanguage / nit.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Merge: Stringify Bytes
[nit.git] / lib / core / bytes.nit
1 # This file is part of NIT ( http://www.nitlanguage.org ).
2 #
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
6 #
7 # http://www.apache.org/licenses/LICENSE-2.0
8 #
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
14
15 # Services for byte streams and arrays
16 module bytes
17
18 import kernel
19 import collection::array
20 intrude import text::flat
21
22 # Any kind of entity which can be searched for in a Sequence of Byte
23 interface BytePattern
24 # Return the first occurence of `self` in `b`, or -1 if not found
25 fun first_index_in(b: SequenceRead[Byte]): Int do return first_index_in_from(b, 0)
26
27 # Return the first occurence of `self` in `b` starting at `from`, or -1 if not found
28 fun first_index_in_from(b: SequenceRead[Byte], from: Int): Int is abstract
29
30 # Return the last occurence of `self` in `b`, or -1 if not found
31 fun last_index_in(b: SequenceRead[Byte]): Int do return last_index_in_from(b, b.length - 1)
32
33 # Return the last occurence of `self` in `b`, or -1 if not found
34 fun last_index_in_from(b: SequenceRead[Byte], from: Int): Int is abstract
35
36 # Returns the indexes of all the occurences of `self` in `b`
37 fun search_all_in(b: SequenceRead[Byte]): SequenceRead[Int] is abstract
38
39 # Length of the pattern
40 fun pattern_length: Int is abstract
41
42 # Appends `self` to `b`
43 fun append_to(b: Sequence[Byte]) is abstract
44
45 # Is `self` a prefix for `b` ?
46 fun is_prefix(b: SequenceRead[Byte]): Bool is abstract
47
48 # Is `self` a suffix for `b` ?
49 fun is_suffix(b: SequenceRead[Byte]): Bool is abstract
50 end
51
52 redef class Byte
53 super BytePattern
54
55 # Write self as a string into `ns` at position `pos`
56 private fun add_digest_at(ns: NativeString, pos: Int) do
57 var tmp = (0xF0u8 & self) >> 4
58 ns[pos] = if tmp >= 0x0Au8 then tmp + 0x37u8 else tmp + 0x30u8
59 tmp = 0x0Fu8 & self
60 ns[pos + 1] = if tmp >= 0x0Au8 then tmp + 0x37u8 else tmp + 0x30u8
61 end
62
63 # Is `self` a valid hexadecimal digit (in ASCII)
64 #
65 # ~~~nit
66 # intrude import core::bytes
67 # assert not '/'.ascii.is_valid_hexdigit
68 # assert '0'.ascii.is_valid_hexdigit
69 # assert '9'.ascii.is_valid_hexdigit
70 # assert not ':'.ascii.is_valid_hexdigit
71 # assert not '@'.ascii.is_valid_hexdigit
72 # assert 'A'.ascii.is_valid_hexdigit
73 # assert 'F'.ascii.is_valid_hexdigit
74 # assert not 'G'.ascii.is_valid_hexdigit
75 # assert not '`'.ascii.is_valid_hexdigit
76 # assert 'a'.ascii.is_valid_hexdigit
77 # assert 'f'.ascii.is_valid_hexdigit
78 # assert not 'g'.ascii.is_valid_hexdigit
79 # ~~~
80 private fun is_valid_hexdigit: Bool do
81 return (self >= 0x30u8 and self <= 0x39u8) or
82 (self >= 0x41u8 and self <= 0x46u8) or
83 (self >= 0x61u8 and self <= 0x66u8)
84 end
85
86 # `self` as a hexdigit to its byte value
87 #
88 # ~~~nit
89 # intrude import core::bytes
90 # assert 0x39u8.hexdigit_to_byteval == 0x09u8
91 # assert 0x43u8.hexdigit_to_byteval == 0x0Cu8
92 # ~~~
93 #
94 # REQUIRE: `self.is_valid_hexdigit`
95 private fun hexdigit_to_byteval: Byte do
96 if self >= 0x30u8 and self <= 0x39u8 then
97 return self - 0x30u8
98 else if self >= 0x41u8 and self <= 0x46u8 then
99 return self - 0x37u8
100 else if self >= 0x61u8 and self <= 0x66u8 then
101 return self - 0x57u8
102 end
103 # Happens only if the requirement is not met.
104 # i.e. this abort is here to please the compiler
105 abort
106 end
107
108 redef fun first_index_in_from(b, from) do
109 for i in [from .. b.length[ do if b[i] == self then return i
110 return -1
111 end
112
113 redef fun last_index_in_from(b, from) do
114 for i in [0 .. from].step(-1) do if b[i] == self then return i
115 return -1
116 end
117
118 redef fun search_all_in(b) do
119 var ret = new Array[Int]
120 var pos = 0
121 loop
122 pos = first_index_in_from(b, pos)
123 if pos == -1 then return ret
124 ret.add pos
125 pos += 1
126 end
127 end
128
129 redef fun pattern_length do return 1
130
131 redef fun append_to(b) do b.push self
132
133 # assert 'b'.ascii.is_suffix("baqsdb".to_bytes)
134 # assert not 'b'.ascii.is_suffix("baqsd".to_bytes)
135 redef fun is_suffix(b) do return b.length != 0 and b.last == self
136
137 # assert 'b'.ascii.is_prefix("baqsdb".to_bytes)
138 # assert not 'b'.ascii.is_prefix("aqsdb".to_bytes)
139 redef fun is_prefix(b) do return b.length != 0 and b.first == self
140 end
141
142 # A buffer containing Byte-manipulation facilities
143 #
144 # Uses Copy-On-Write when persisted
145 class Bytes
146 super AbstractArray[Byte]
147 super BytePattern
148
149 # A NativeString being a char*, it can be used as underlying representation here.
150 var items: NativeString
151
152 # Number of bytes in the array
153 redef var length
154
155 # Capacity of the array
156 private var capacity: Int
157
158 # Has this buffer been persisted (to_s'd)?
159 #
160 # Used for Copy-On-Write
161 private var persisted = false
162
163 # var b = new Bytes.empty
164 # assert b.to_s == ""
165 init empty do
166 var ns = new NativeString(0)
167 init(ns, 0, 0)
168 end
169
170 # Init a `Bytes` with capacity `cap`
171 init with_capacity(cap: Int) do
172 var ns = new NativeString(cap)
173 init(ns, 0, cap)
174 end
175
176 redef fun pattern_length do return length
177
178 redef fun is_empty do return length == 0
179
180 # var b = new Bytes.empty
181 # b.add 101u8
182 # assert b[0] == 101u8
183 redef fun [](i) do
184 assert i >= 0
185 assert i < length
186 return items[i]
187 end
188
189 # Returns a copy of `self`
190 fun clone: Bytes do
191 var b = new Bytes.with_capacity(length)
192 b.append(self)
193 return b
194 end
195
196 # Trims off the whitespaces at the beginning and the end of `self`
197 #
198 # var b = "102041426E6F1020" .hexdigest_to_bytes
199 # assert b.trim.hexdigest == "41426E6F"
200 #
201 # NOTE: A whitespace is defined here as a byte whose value is <= 0x20
202 fun trim: Bytes do
203 var st = 0
204 while st < length do
205 if self[st] > 0x20u8 then break
206 st += 1
207 end
208 if st >= length then return new Bytes.empty
209 var ed = length - 1
210 while ed > 0 do
211 if self[ed] > 0x20u8 then break
212 ed -= 1
213 end
214 return slice(st, ed - st + 1)
215 end
216
217 # Returns a subset of the content of `self` starting at `from` and of length `count`
218 #
219 # var b = "abcd".to_bytes
220 # assert b.slice(1, 2).hexdigest == "6263"
221 # assert b.slice(-1, 2).hexdigest == "61"
222 # assert b.slice(1, 0).hexdigest == ""
223 # assert b.slice(2, 5).hexdigest == "6364"
224 fun slice(from, count: Int): Bytes do
225 if count <= 0 then return new Bytes.empty
226
227 if from < 0 then
228 count += from
229 if count < 0 then count = 0
230 from = 0
231 end
232
233 if (count + from) > length then count = length - from
234 if count <= 0 then return new Bytes.empty
235
236 var ret = new Bytes.with_capacity(count)
237
238 ret.append_ns(items.fast_cstring(from), count)
239 return ret
240 end
241
242 # Returns a copy of `self` starting at `from`
243 #
244 # var b = "abcd".to_bytes
245 # assert b.slice_from(1).hexdigest == "626364"
246 # assert b.slice_from(-1).hexdigest == "61626364"
247 # assert b.slice_from(2).hexdigest == "6364"
248 fun slice_from(from: Int): Bytes do
249 if from >= length then return new Bytes.empty
250 if from < 0 then from = 0
251 return slice(from, length)
252 end
253
254 # Returns self as a hexadecimal digest
255 fun hexdigest: String do
256 var elen = length * 2
257 var ns = new NativeString(elen)
258 var i = 0
259 var oi = 0
260 while i < length do
261 self[i].add_digest_at(ns, oi)
262 i += 1
263 oi += 2
264 end
265 return new FlatString.full(ns, elen, 0, elen - 1, elen)
266 end
267
268 # var b = new Bytes.with_capacity(1)
269 # b[0] = 101u8
270 # assert b.to_s == "e"
271 redef fun []=(i, v) do
272 if persisted then regen
273 assert i >= 0
274 assert i <= length
275 if i == length then add(v)
276 items[i] = v
277 end
278
279 # var b = new Bytes.empty
280 # b.add 101u8
281 # assert b.to_s == "e"
282 redef fun add(c) do
283 if persisted then regen
284 if length >= capacity then
285 enlarge(length)
286 end
287 items[length] = c
288 length += 1
289 end
290
291 # Adds the UTF-8 representation of `c` to `self`
292 #
293 # var b = new Bytes.empty
294 # b.add_char('A')
295 # b.add_char('キ')
296 # assert b.hexdigest == "41E382AD"
297 fun add_char(c: Char) do
298 if persisted then regen
299 var cln = c.u8char_len
300 var ln = length
301 enlarge(ln + cln)
302 items.set_char_at(length, c)
303 length += cln
304 end
305
306 # var b = new Bytes.empty
307 # b.append([104u8, 101u8, 108u8, 108u8, 111u8])
308 # assert b.to_s == "hello"
309 redef fun append(arr) do
310 if arr isa Bytes then
311 append_ns(arr.items, arr.length)
312 else
313 for i in arr do add i
314 end
315 end
316
317 # var b = new Bytes.empty
318 # b.append([0x41u8, 0x41u8, 0x18u8])
319 # b.pop
320 # assert b.to_s == "AA"
321 redef fun pop do
322 assert length >= 1
323 length -= 1
324 return items[length]
325 end
326
327 redef fun clear do length = 0
328
329 # Regenerates the buffer, necessary when it was persisted
330 private fun regen do
331 var nns = new NativeString(capacity)
332 items.copy_to(nns, length, 0, 0)
333 persisted = false
334 end
335
336 # Appends the `ln` first bytes of `ns` to self
337 fun append_ns(ns: NativeString, ln: Int) do
338 if persisted then regen
339 var nlen = length + ln
340 if nlen > capacity then enlarge(nlen)
341 ns.copy_to(items, ln, 0, length)
342 length += ln
343 end
344
345 # Appends `ln` bytes from `ns` starting at index `from` to self
346 fun append_ns_from(ns: NativeString, ln, from: Int) do
347 if persisted then regen
348 var nlen = length + ln
349 if nlen > capacity then enlarge(nlen)
350 ns.copy_to(items, ln, from, length)
351 length += ln
352 end
353
354 # Appends the bytes of `s` to `selftextextt`
355 fun append_text(s: Text) do
356 for i in s.substrings do
357 append_ns(i.fast_cstring, i.bytelen)
358 end
359 end
360
361 redef fun append_to(b) do b.append self
362
363 redef fun enlarge(sz) do
364 if capacity >= sz then return
365 persisted = false
366 while capacity < sz do capacity = capacity * 2 + 2
367 var ns = new NativeString(capacity)
368 items.copy_to(ns, length, 0, 0)
369 items = ns
370 end
371
372 redef fun to_s do
373 persisted = true
374 var b = self
375 var r = b.items.to_s_with_length(length)
376 if r != items then persisted = false
377 return r
378 end
379
380 redef fun iterator do return new BytesIterator.with_buffer(self)
381
382 redef fun first_index_in_from(b, from) do
383 if is_empty then return -1
384 var fst = self[0]
385 var bpos = fst.first_index_in_from(self, from)
386 for i in [0 .. length[ do
387 if self[i] != b[bpos] then return first_index_in_from(b, bpos + 1)
388 bpos += 1
389 end
390 return bpos
391 end
392
393 redef fun last_index_in_from(b, from) do
394 if is_empty then return -1
395 var lst = self[length - 1]
396 var bpos = lst.last_index_in_from(b, from)
397 for i in [0 .. length[.step(-1) do
398 if self[i] != b[bpos] then return last_index_in_from(b, bpos - 1)
399 bpos -= 1
400 end
401 return bpos
402 end
403
404 redef fun search_all_in(b) do
405 var ret = new Array[Int]
406 var pos = first_index_in_from(b, 0)
407 if pos == -1 then return ret
408 pos = pos + 1
409 ret.add pos
410 loop
411 pos = first_index_in_from(b, pos)
412 if pos == -1 then return ret
413 ret.add pos
414 pos += length
415 end
416 end
417
418 # Splits the content on self when encountering `b`
419 #
420 # var a = "String is string".to_bytes.split_with('s'.ascii)
421 # assert a.length == 3
422 # assert a[0].hexdigest == "537472696E672069"
423 # assert a[1].hexdigest == "20"
424 # assert a[2].hexdigest == "7472696E67"
425 fun split_with(b: BytePattern): Array[Bytes] do
426 var fst = b.search_all_in(self)
427 if fst.is_empty then return [clone]
428 var retarr = new Array[Bytes]
429 var prev = 0
430 for i in fst do
431 retarr.add(slice(prev, i - prev))
432 prev = i + b.pattern_length
433 end
434 retarr.add slice_from(prev)
435 return retarr
436 end
437
438 # Splits `self` in two parts at the first occurence of `b`
439 #
440 # var a = "String is string".to_bytes.split_once_on('s'.ascii)
441 # assert a[0].hexdigest == "537472696E672069"
442 # assert a[1].hexdigest == "20737472696E67"
443 fun split_once_on(b: BytePattern): Array[Bytes] do
444 var spl = b.first_index_in(self)
445 if spl == -1 then return [clone]
446 var ret = new Array[Bytes].with_capacity(2)
447 ret.add(slice(0, spl))
448 ret.add(slice_from(spl + b.pattern_length))
449 return ret
450 end
451
452 # Replaces all the occurences of `this` in `self` by `by`
453 #
454 # var b = "String is string".to_bytes.replace(0x20u8, 0x41u8)
455 # assert b.hexdigest == "537472696E6741697341737472696E67"
456 fun replace(pattern: BytePattern, bytes: BytePattern): Bytes do
457 if is_empty then return new Bytes.empty
458 var pos = pattern.search_all_in(self)
459 if pos.is_empty then return clone
460 var ret = new Bytes.with_capacity(length)
461 var prev = 0
462 for i in pos do
463 ret.append_ns(items.fast_cstring(prev), i - prev)
464 bytes.append_to ret
465 prev = i + pattern.pattern_length
466 end
467 ret.append(slice_from(pos.last + pattern.pattern_length))
468 return ret
469 end
470
471 # Decode `self` from percent (or URL) encoding to a clear string
472 #
473 # Replace invalid use of '%' with '?'.
474 #
475 # assert "aBc09-._~".to_bytes.from_percent_encoding == "aBc09-._~".to_bytes
476 # assert "%25%28%29%3c%20%3e".to_bytes.from_percent_encoding == "%()< >".to_bytes
477 # assert ".com%2fpost%3fe%3dasdf%26f%3d123".to_bytes.from_percent_encoding == ".com/post?e=asdf&f=123".to_bytes
478 # assert "%25%28%29%3C%20%3E".to_bytes.from_percent_encoding == "%()< >".to_bytes
479 # assert "incomplete %".to_bytes.from_percent_encoding == "incomplete ?".to_bytes
480 # assert "invalid % usage".to_bytes.from_percent_encoding == "invalid ? usage".to_bytes
481 # assert "%c3%a9%e3%81%82%e3%81%84%e3%81%86".to_bytes.from_percent_encoding == "éあいう".to_bytes
482 fun from_percent_encoding: Bytes do
483 var tmp = new Bytes.with_capacity(length)
484 var pos = 0
485 while pos < length do
486 var b = self[pos]
487 if b != '%'.ascii then
488 tmp.add b
489 pos += 1
490 continue
491 end
492 if length - pos < 2 then
493 tmp.add '?'.ascii
494 pos += 1
495 continue
496 end
497 var bn = self[pos + 1]
498 var bnn = self[pos + 2]
499 if not bn.is_valid_hexdigit or not bnn.is_valid_hexdigit then
500 tmp.add '?'.ascii
501 pos += 1
502 continue
503 end
504 tmp.add((bn.hexdigit_to_byteval << 4) + bnn.hexdigit_to_byteval)
505 pos += 3
506 end
507 return tmp
508 end
509
510 # Is `b` a prefix of `self` ?
511 fun has_prefix(b: BytePattern): Bool do return b.is_prefix(self)
512
513 # Is `b` a suffix of `self` ?
514 fun has_suffix(b: BytePattern): Bool do return b.is_suffix(self)
515
516 redef fun is_suffix(b) do
517 if length > b.length then return false
518 var j = b.length - 1
519 var i = length - 1
520 while i > 0 do
521 if self[i] != b[j] then return false
522 i -= 1
523 j -= 1
524 end
525 return true
526 end
527
528 redef fun is_prefix(b) do
529 if length > b.length then return false
530 for i in [0 .. length[ do if self[i] != b[i] then return false
531 return true
532 end
533 end
534
535 private class BytesIterator
536 super IndexedIterator[Byte]
537
538 var tgt: NativeString
539
540 redef var index
541
542 var max: Int
543
544 init with_buffer(b: Bytes) do init(b.items, 0, b.length)
545
546 redef fun is_ok do return index < max
547
548 redef fun next do index += 1
549
550 redef fun item do return tgt[index]
551 end
552
553 redef class Text
554 # Returns a mutable copy of `self`'s bytes
555 #
556 # ~~~nit
557 # assert "String".to_bytes isa Bytes
558 # assert "String".to_bytes == [83u8, 116u8, 114u8, 105u8, 110u8, 103u8]
559 # ~~~
560 fun to_bytes: Bytes do
561 var b = new Bytes.with_capacity(bytelen)
562 append_to_bytes b
563 return b
564 end
565
566 # Is `self` a valid hexdigest ?
567 #
568 # assert "0B1d3F".is_valid_hexdigest
569 # assert not "5G".is_valid_hexdigest
570 fun is_valid_hexdigest: Bool do
571 for i in bytes do if not i.is_valid_hexdigit then return false
572 return true
573 end
574
575 # Appends `self.bytes` to `b`
576 fun append_to_bytes(b: Bytes) do
577 for s in substrings do
578 var from = if s isa FlatString then s.first_byte else 0
579 b.append_ns_from(s.items, s.bytelen, from)
580 end
581 end
582
583 # Returns a new `Bytes` instance with the digest as content
584 #
585 # assert "0B1F4D".hexdigest_to_bytes == [0x0Bu8, 0x1Fu8, 0x4Du8]
586 #
587 # REQUIRE: `self` is a valid hexdigest and hexdigest.length % 2 == 0
588 fun hexdigest_to_bytes: Bytes do
589 var b = bytes
590 var pos = 0
591 var max = bytelen
592 var ret = new Bytes.with_capacity(max / 2)
593 while pos < max do
594 ret.add((b[pos].hexdigit_to_byteval << 4) |
595 b[pos + 1].hexdigit_to_byteval)
596 pos += 2
597 end
598 return ret
599 end
600
601 # Gets the hexdigest of the bytes of `self`
602 #
603 # assert "&lt;STRING&#47;&rt;".hexdigest == "266C743B535452494E47262334373B2672743B"
604 fun hexdigest: String do
605 var ln = bytelen
606 var outns = new NativeString(ln * 2)
607 var oi = 0
608 for i in [0 .. ln[ do
609 bytes[i].add_digest_at(outns, oi)
610 oi += 2
611 end
612 return new FlatString.with_infos(outns, ln * 2, 0, ln * 2 - 1)
613 end
614
615 # Return a `Bytes` instance where Nit escape sequences are transformed.
616 #
617 # assert "B\\n\\x41\\u0103D3".unescape_to_bytes.hexdigest == "420A41F0908F93"
618 fun unescape_to_bytes: Bytes do
619 var res = new Bytes.with_capacity(self.bytelen)
620 var was_slash = false
621 var i = 0
622 while i < length do
623 var c = chars[i]
624 if not was_slash then
625 if c == '\\' then
626 was_slash = true
627 else
628 res.add_char(c)
629 end
630 i += 1
631 continue
632 end
633 was_slash = false
634 if c == 'n' then
635 res.add_char('\n')
636 else if c == 'r' then
637 res.add_char('\r')
638 else if c == 't' then
639 res.add_char('\t')
640 else if c == '0' then
641 res.add_char('\0')
642 else if c == 'x' or c == 'X' then
643 var hx = substring(i + 1, 2)
644 if hx.is_hex then
645 res.add(hx.to_hex.to_b)
646 else
647 res.add_char(c)
648 end
649 i += 2
650 else if c == 'u' or c == 'U' then
651 var hx = substring(i + 1, 6)
652 if hx.is_hex then
653 res.add_char(hx.to_hex.code_point)
654 else
655 res.add_char(c)
656 end
657 i += 6
658 else
659 res.add_char(c)
660 end
661 i += 1
662 end
663 return res
664 end
665 end
666
667 redef class FlatText
668 redef fun append_to_bytes(b) do
669 var from = if self isa FlatString then first_byte else 0
670 b.append_ns_from(items, bytelen, from)
671 end
672 end
673
674 redef class NativeString
675 # Creates a new `Bytes` object from `self` with `len` as length
676 #
677 # If `len` is null, strlen will determine the length of the Bytes
678 fun to_bytes(len: nullable Int): Bytes do
679 if len == null then len = cstring_length
680 return new Bytes(self, len, len)
681 end
682
683 # Creates a new `Bytes` object from a copy of `self` with `len` as length
684 #
685 # If `len` is null, strlen will determine the length of the Bytes
686 fun to_bytes_with_copy(len: nullable Int): Bytes do
687 if len == null then len = cstring_length
688 var nns = new NativeString(len)
689 copy_to(nns, len, 0, 0)
690 return new Bytes(nns, len, len)
691 end
692 end
693
694 # Joins an array of bytes `arr` separated by `sep`
695 #
696 # assert join_bytes(["String".to_bytes, "is".to_bytes, "string".to_bytes], ' '.ascii).hexdigest == "537472696E6720697320737472696E67"
697 fun join_bytes(arr: Array[Bytes], sep: nullable BytePattern): Bytes do
698 if arr.is_empty then return new Bytes.empty
699 sep = sep or else new Bytes.empty
700 var endln = sep.pattern_length * (arr.length - 1)
701 for i in arr do endln += i.length
702 var ret = new Bytes.with_capacity(endln)
703 ret.append(arr.first)
704 for i in [1 .. arr.length[ do
705 sep.append_to(ret)
706 ret.append arr[i]
707 end
708 return ret
709 end
Nit language project; an oo programing language and its tool suite.