nitlanguage / nit.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
core/bytes: document hexdigest
[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 an hexadecimal digest.
255 #
256 # Also known as plain hexdump or postscript hexdump.
257 #
258 # ~~~
259 # var b = "abcd".to_bytes
260 # assert b.hexdigest == "61626364"
261 # assert b.hexdigest.hexdigest_to_bytes == b
262 # ~~~
263 fun hexdigest: String do
264 var elen = length * 2
265 var ns = new NativeString(elen)
266 var i = 0
267 var oi = 0
268 while i < length do
269 self[i].add_digest_at(ns, oi)
270 i += 1
271 oi += 2
272 end
273 return new FlatString.full(ns, elen, 0, elen)
274 end
275
276 # var b = new Bytes.with_capacity(1)
277 # b[0] = 101u8
278 # assert b.to_s == "e"
279 redef fun []=(i, v) do
280 if persisted then regen
281 assert i >= 0
282 assert i <= length
283 if i == length then add(v)
284 items[i] = v
285 end
286
287 # var b = new Bytes.empty
288 # b.add 101u8
289 # assert b.to_s == "e"
290 redef fun add(c) do
291 if persisted then regen
292 if length >= capacity then
293 enlarge(length)
294 end
295 items[length] = c
296 length += 1
297 end
298
299 # Adds the UTF-8 representation of `c` to `self`
300 #
301 # var b = new Bytes.empty
302 # b.add_char('A')
303 # b.add_char('キ')
304 # assert b.hexdigest == "41E382AD"
305 fun add_char(c: Char) do
306 if persisted then regen
307 var cln = c.u8char_len
308 var ln = length
309 enlarge(ln + cln)
310 items.set_char_at(length, c)
311 length += cln
312 end
313
314 # var b = new Bytes.empty
315 # b.append([104u8, 101u8, 108u8, 108u8, 111u8])
316 # assert b.to_s == "hello"
317 redef fun append(arr) do
318 if arr isa Bytes then
319 append_ns(arr.items, arr.length)
320 else
321 for i in arr do add i
322 end
323 end
324
325 # var b = new Bytes.empty
326 # b.append([0x41u8, 0x41u8, 0x18u8])
327 # b.pop
328 # assert b.to_s == "AA"
329 redef fun pop do
330 assert length >= 1
331 length -= 1
332 return items[length]
333 end
334
335 redef fun clear do length = 0
336
337 # Regenerates the buffer, necessary when it was persisted
338 private fun regen do
339 var nns = new NativeString(capacity)
340 items.copy_to(nns, length, 0, 0)
341 persisted = false
342 end
343
344 # Appends the `ln` first bytes of `ns` to self
345 fun append_ns(ns: NativeString, ln: Int) do
346 if persisted then regen
347 var nlen = length + ln
348 if nlen > capacity then enlarge(nlen)
349 ns.copy_to(items, ln, 0, length)
350 length += ln
351 end
352
353 # Appends `ln` bytes from `ns` starting at index `from` to self
354 fun append_ns_from(ns: NativeString, ln, from: Int) do
355 if persisted then regen
356 var nlen = length + ln
357 if nlen > capacity then enlarge(nlen)
358 ns.copy_to(items, ln, from, length)
359 length += ln
360 end
361
362 # Appends the bytes of `s` to `selftextextt`
363 fun append_text(s: Text) do
364 for i in s.substrings do
365 append_ns(i.fast_cstring, i.bytelen)
366 end
367 end
368
369 redef fun append_to(b) do b.append self
370
371 redef fun enlarge(sz) do
372 if capacity >= sz then return
373 persisted = false
374 while capacity < sz do capacity = capacity * 2 + 2
375 var ns = new NativeString(capacity)
376 items.copy_to(ns, length, 0, 0)
377 items = ns
378 end
379
380 redef fun to_s do
381 persisted = true
382 var b = self
383 var r = b.items.to_s_with_length(length)
384 if r != items then persisted = false
385 return r
386 end
387
388 redef fun iterator do return new BytesIterator.with_buffer(self)
389
390 redef fun first_index_in_from(b, from) do
391 if is_empty then return -1
392 var fst = self[0]
393 var bpos = fst.first_index_in_from(self, from)
394 for i in [0 .. length[ do
395 if self[i] != b[bpos] then return first_index_in_from(b, bpos + 1)
396 bpos += 1
397 end
398 return bpos
399 end
400
401 redef fun last_index_in_from(b, from) do
402 if is_empty then return -1
403 var lst = self[length - 1]
404 var bpos = lst.last_index_in_from(b, from)
405 for i in [0 .. length[.step(-1) do
406 if self[i] != b[bpos] then return last_index_in_from(b, bpos - 1)
407 bpos -= 1
408 end
409 return bpos
410 end
411
412 redef fun search_all_in(b) do
413 var ret = new Array[Int]
414 var pos = first_index_in_from(b, 0)
415 if pos == -1 then return ret
416 pos = pos + 1
417 ret.add pos
418 loop
419 pos = first_index_in_from(b, pos)
420 if pos == -1 then return ret
421 ret.add pos
422 pos += length
423 end
424 end
425
426 # Splits the content on self when encountering `b`
427 #
428 # var a = "String is string".to_bytes.split_with('s'.ascii)
429 # assert a.length == 3
430 # assert a[0].hexdigest == "537472696E672069"
431 # assert a[1].hexdigest == "20"
432 # assert a[2].hexdigest == "7472696E67"
433 fun split_with(b: BytePattern): Array[Bytes] do
434 var fst = b.search_all_in(self)
435 if fst.is_empty then return [clone]
436 var retarr = new Array[Bytes]
437 var prev = 0
438 for i in fst do
439 retarr.add(slice(prev, i - prev))
440 prev = i + b.pattern_length
441 end
442 retarr.add slice_from(prev)
443 return retarr
444 end
445
446 # Splits `self` in two parts at the first occurence of `b`
447 #
448 # var a = "String is string".to_bytes.split_once_on('s'.ascii)
449 # assert a[0].hexdigest == "537472696E672069"
450 # assert a[1].hexdigest == "20737472696E67"
451 fun split_once_on(b: BytePattern): Array[Bytes] do
452 var spl = b.first_index_in(self)
453 if spl == -1 then return [clone]
454 var ret = new Array[Bytes].with_capacity(2)
455 ret.add(slice(0, spl))
456 ret.add(slice_from(spl + b.pattern_length))
457 return ret
458 end
459
460 # Replaces all the occurences of `this` in `self` by `by`
461 #
462 # var b = "String is string".to_bytes.replace(0x20u8, 0x41u8)
463 # assert b.hexdigest == "537472696E6741697341737472696E67"
464 fun replace(pattern: BytePattern, bytes: BytePattern): Bytes do
465 if is_empty then return new Bytes.empty
466 var pos = pattern.search_all_in(self)
467 if pos.is_empty then return clone
468 var ret = new Bytes.with_capacity(length)
469 var prev = 0
470 for i in pos do
471 ret.append_ns(items.fast_cstring(prev), i - prev)
472 bytes.append_to ret
473 prev = i + pattern.pattern_length
474 end
475 ret.append(slice_from(pos.last + pattern.pattern_length))
476 return ret
477 end
478
479 # Decode `self` from percent (or URL) encoding to a clear string
480 #
481 # Replace invalid use of '%' with '?'.
482 #
483 # assert "aBc09-._~".to_bytes.from_percent_encoding == "aBc09-._~".to_bytes
484 # assert "%25%28%29%3c%20%3e".to_bytes.from_percent_encoding == "%()< >".to_bytes
485 # assert ".com%2fpost%3fe%3dasdf%26f%3d123".to_bytes.from_percent_encoding == ".com/post?e=asdf&f=123".to_bytes
486 # assert "%25%28%29%3C%20%3E".to_bytes.from_percent_encoding == "%()< >".to_bytes
487 # assert "incomplete %".to_bytes.from_percent_encoding == "incomplete ?".to_bytes
488 # assert "invalid % usage".to_bytes.from_percent_encoding == "invalid ? usage".to_bytes
489 # assert "%c3%a9%e3%81%82%e3%81%84%e3%81%86".to_bytes.from_percent_encoding == "éあいう".to_bytes
490 fun from_percent_encoding: Bytes do
491 var tmp = new Bytes.with_capacity(length)
492 var pos = 0
493 while pos < length do
494 var b = self[pos]
495 if b != '%'.ascii then
496 tmp.add b
497 pos += 1
498 continue
499 end
500 if length - pos < 2 then
501 tmp.add '?'.ascii
502 pos += 1
503 continue
504 end
505 var bn = self[pos + 1]
506 var bnn = self[pos + 2]
507 if not bn.is_valid_hexdigit or not bnn.is_valid_hexdigit then
508 tmp.add '?'.ascii
509 pos += 1
510 continue
511 end
512 tmp.add((bn.hexdigit_to_byteval << 4) + bnn.hexdigit_to_byteval)
513 pos += 3
514 end
515 return tmp
516 end
517
518 # Is `b` a prefix of `self` ?
519 fun has_prefix(b: BytePattern): Bool do return b.is_prefix(self)
520
521 # Is `b` a suffix of `self` ?
522 fun has_suffix(b: BytePattern): Bool do return b.is_suffix(self)
523
524 redef fun is_suffix(b) do
525 if length > b.length then return false
526 var j = b.length - 1
527 var i = length - 1
528 while i > 0 do
529 if self[i] != b[j] then return false
530 i -= 1
531 j -= 1
532 end
533 return true
534 end
535
536 redef fun is_prefix(b) do
537 if length > b.length then return false
538 for i in [0 .. length[ do if self[i] != b[i] then return false
539 return true
540 end
541 end
542
543 private class BytesIterator
544 super IndexedIterator[Byte]
545
546 var tgt: NativeString
547
548 redef var index
549
550 var max: Int
551
552 init with_buffer(b: Bytes) do init(b.items, 0, b.length)
553
554 redef fun is_ok do return index < max
555
556 redef fun next do index += 1
557
558 redef fun item do return tgt[index]
559 end
560
561 redef class Text
562 # Returns a mutable copy of `self`'s bytes
563 #
564 # ~~~nit
565 # assert "String".to_bytes isa Bytes
566 # assert "String".to_bytes == [83u8, 116u8, 114u8, 105u8, 110u8, 103u8]
567 # ~~~
568 fun to_bytes: Bytes do
569 var b = new Bytes.with_capacity(bytelen)
570 append_to_bytes b
571 return b
572 end
573
574 # Is `self` a valid hexdigest ?
575 #
576 # assert "0B1d3F".is_valid_hexdigest
577 # assert not "5G".is_valid_hexdigest
578 fun is_valid_hexdigest: Bool do
579 for i in bytes do if not i.is_valid_hexdigit then return false
580 return true
581 end
582
583 # Appends `self.bytes` to `b`
584 fun append_to_bytes(b: Bytes) do
585 for s in substrings do
586 var from = if s isa FlatString then s.first_byte else 0
587 b.append_ns_from(s.items, s.bytelen, from)
588 end
589 end
590
591 # Returns a new `Bytes` instance with the digest as content
592 #
593 # assert "0B1F4D".hexdigest_to_bytes == [0x0Bu8, 0x1Fu8, 0x4Du8]
594 # assert "0B1F4D".hexdigest_to_bytes.hexdigest == "0B1F4D"
595 #
596 # REQUIRE: `self` is a valid hexdigest and hexdigest.length % 2 == 0
597 fun hexdigest_to_bytes: Bytes do
598 var b = bytes
599 var pos = 0
600 var max = bytelen
601 var ret = new Bytes.with_capacity(max / 2)
602 while pos < max do
603 ret.add((b[pos].hexdigit_to_byteval << 4) |
604 b[pos + 1].hexdigit_to_byteval)
605 pos += 2
606 end
607 return ret
608 end
609
610 # Gets the hexdigest of the bytes of `self`
611 #
612 # assert "&lt;STRING&#47;&rt;".hexdigest == "266C743B535452494E47262334373B2672743B"
613 fun hexdigest: String do
614 var ln = bytelen
615 var outns = new NativeString(ln * 2)
616 var oi = 0
617 for i in [0 .. ln[ do
618 bytes[i].add_digest_at(outns, oi)
619 oi += 2
620 end
621 return new FlatString.with_infos(outns, ln * 2, 0)
622 end
623
624 # Return a `Bytes` instance where Nit escape sequences are transformed.
625 #
626 # assert "B\\n\\x41\\u0103D3".unescape_to_bytes.hexdigest == "420A41F0908F93"
627 fun unescape_to_bytes: Bytes do
628 var res = new Bytes.with_capacity(self.bytelen)
629 var was_slash = false
630 var i = 0
631 while i < length do
632 var c = chars[i]
633 if not was_slash then
634 if c == '\\' then
635 was_slash = true
636 else
637 res.add_char(c)
638 end
639 i += 1
640 continue
641 end
642 was_slash = false
643 if c == 'n' then
644 res.add_char('\n')
645 else if c == 'r' then
646 res.add_char('\r')
647 else if c == 't' then
648 res.add_char('\t')
649 else if c == '0' then
650 res.add_char('\0')
651 else if c == 'x' or c == 'X' then
652 var hx = substring(i + 1, 2)
653 if hx.is_hex then
654 res.add(hx.to_hex.to_b)
655 else
656 res.add_char(c)
657 end
658 i += 2
659 else if c == 'u' or c == 'U' then
660 var hx = substring(i + 1, 6)
661 if hx.is_hex then
662 res.add_char(hx.to_hex.code_point)
663 else
664 res.add_char(c)
665 end
666 i += 6
667 else
668 res.add_char(c)
669 end
670 i += 1
671 end
672 return res
673 end
674 end
675
676 redef class FlatText
677 redef fun append_to_bytes(b) do
678 var from = if self isa FlatString then first_byte else 0
679 b.append_ns_from(items, bytelen, from)
680 end
681 end
682
683 redef class NativeString
684 # Creates a new `Bytes` object from `self` with `len` as length
685 #
686 # If `len` is null, strlen will determine the length of the Bytes
687 fun to_bytes(len: nullable Int): Bytes do
688 if len == null then len = cstring_length
689 return new Bytes(self, len, len)
690 end
691
692 # Creates a new `Bytes` object from a copy of `self` with `len` as length
693 #
694 # If `len` is null, strlen will determine the length of the Bytes
695 fun to_bytes_with_copy(len: nullable Int): Bytes do
696 if len == null then len = cstring_length
697 var nns = new NativeString(len)
698 copy_to(nns, len, 0, 0)
699 return new Bytes(nns, len, len)
700 end
701 end
702
703 # Joins an array of bytes `arr` separated by `sep`
704 #
705 # assert join_bytes(["String".to_bytes, "is".to_bytes, "string".to_bytes], ' '.ascii).hexdigest == "537472696E6720697320737472696E67"
706 fun join_bytes(arr: Array[Bytes], sep: nullable BytePattern): Bytes do
707 if arr.is_empty then return new Bytes.empty
708 sep = sep or else new Bytes.empty
709 var endln = sep.pattern_length * (arr.length - 1)
710 for i in arr do endln += i.length
711 var ret = new Bytes.with_capacity(endln)
712 ret.append(arr.first)
713 for i in [1 .. arr.length[ do
714 sep.append_to(ret)
715 ret.append arr[i]
716 end
717 return ret
718 end
Nit language project; an oo programing language and its tool suite.