build: introduce luci-base
[project/luci.git] / modules / base / luasrc / util.lua
1 --[[
2 LuCI - Utility library
3
4 Description:
5 Several common useful Lua functions
6
7 License:
8 Copyright 2008 Steven Barth <steven@midlink.org>
9
10 Licensed under the Apache License, Version 2.0 (the "License");
11 you may not use this file except in compliance with the License.
12 You may obtain a copy of the License at
13
14         http://www.apache.org/licenses/LICENSE-2.0
15
16 Unless required by applicable law or agreed to in writing, software
17 distributed under the License is distributed on an "AS IS" BASIS,
18 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 See the License for the specific language governing permissions and
20 limitations under the License.
21
22 ]]--
23
24 local io = require "io"
25 local math = require "math"
26 local table = require "table"
27 local debug = require "debug"
28 local ldebug = require "luci.debug"
29 local string = require "string"
30 local coroutine = require "coroutine"
31 local tparser = require "luci.template.parser"
32
33 local getmetatable, setmetatable = getmetatable, setmetatable
34 local rawget, rawset, unpack = rawget, rawset, unpack
35 local tostring, type, assert = tostring, type, assert
36 local ipairs, pairs, next, loadstring = ipairs, pairs, next, loadstring
37 local require, pcall, xpcall = require, pcall, xpcall
38 local collectgarbage, get_memory_limit = collectgarbage, get_memory_limit
39
40 --- LuCI utility functions.
41 module "luci.util"
42
43 --
44 -- Pythonic string formatting extension
45 --
46 getmetatable("").__mod = function(a, b)
47         if not b then
48                 return a
49         elseif type(b) == "table" then
50                 for k, _ in pairs(b) do if type(b[k]) == "userdata" then b[k] = tostring(b[k]) end end
51                 return a:format(unpack(b))
52         else
53                 if type(b) == "userdata" then b = tostring(b) end
54                 return a:format(b)
55         end
56 end
57
58
59 --
60 -- Class helper routines
61 --
62
63 -- Instantiates a class
64 local function _instantiate(class, ...)
65         local inst = setmetatable({}, {__index = class})
66
67         if inst.__init__ then
68                 inst:__init__(...)
69         end
70
71         return inst
72 end
73
74 --- Create a Class object (Python-style object model).
75 -- The class object can be instantiated by calling itself.
76 -- Any class functions or shared parameters can be attached to this object.
77 -- Attaching a table to the class object makes this table shared between
78 -- all instances of this class. For object parameters use the __init__ function.
79 -- Classes can inherit member functions and values from a base class.
80 -- Class can be instantiated by calling them. All parameters will be passed
81 -- to the __init__ function of this class - if such a function exists.
82 -- The __init__ function must be used to set any object parameters that are not shared
83 -- with other objects of this class. Any return values will be ignored.
84 -- @param base  The base class to inherit from (optional)
85 -- @return              A class object
86 -- @see                 instanceof
87 -- @see                 clone
88 function class(base)
89         return setmetatable({}, {
90                 __call  = _instantiate,
91                 __index = base
92         })
93 end
94
95 --- Test whether the given object is an instance of the given class.
96 -- @param object        Object instance
97 -- @param class         Class object to test against
98 -- @return                      Boolean indicating whether the object is an instance
99 -- @see                         class
100 -- @see                         clone
101 function instanceof(object, class)
102         local meta = getmetatable(object)
103         while meta and meta.__index do
104                 if meta.__index == class then
105                         return true
106                 end
107                 meta = getmetatable(meta.__index)
108         end
109         return false
110 end
111
112
113 --
114 -- Scope manipulation routines
115 --
116
117 local tl_meta = {
118         __mode = "k",
119
120         __index = function(self, key)
121                 local t = rawget(self, coxpt[coroutine.running()]
122                  or coroutine.running() or 0)
123                 return t and t[key]
124         end,
125
126         __newindex = function(self, key, value)
127                 local c = coxpt[coroutine.running()] or coroutine.running() or 0
128                 if not rawget(self, c) then
129                         rawset(self, c, { [key] = value })
130                 else
131                         rawget(self, c)[key] = value
132                 end
133         end
134 }
135
136 --- Create a new or get an already existing thread local store associated with
137 -- the current active coroutine. A thread local store is private a table object
138 -- whose values can't be accessed from outside of the running coroutine.
139 -- @return      Table value representing the corresponding thread local store
140 function threadlocal(tbl)
141         return setmetatable(tbl or {}, tl_meta)
142 end
143
144
145 --
146 -- Debugging routines
147 --
148
149 --- Write given object to stderr.
150 -- @param obj   Value to write to stderr
151 -- @return              Boolean indicating whether the write operation was successful
152 function perror(obj)
153         return io.stderr:write(tostring(obj) .. "\n")
154 end
155
156 --- Recursively dumps a table to stdout, useful for testing and debugging.
157 -- @param t     Table value to dump
158 -- @param maxdepth      Maximum depth
159 -- @return      Always nil
160 function dumptable(t, maxdepth, i, seen)
161         i = i or 0
162         seen = seen or setmetatable({}, {__mode="k"})
163
164         for k,v in pairs(t) do
165                 perror(string.rep("\t", i) .. tostring(k) .. "\t" .. tostring(v))
166                 if type(v) == "table" and (not maxdepth or i < maxdepth) then
167                         if not seen[v] then
168                                 seen[v] = true
169                                 dumptable(v, maxdepth, i+1, seen)
170                         else
171                                 perror(string.rep("\t", i) .. "*** RECURSION ***")
172                         end
173                 end
174         end
175 end
176
177
178 --
179 -- String and data manipulation routines
180 --
181
182 --- Create valid XML PCDATA from given string.
183 -- @param value String value containing the data to escape
184 -- @return              String value containing the escaped data
185 function pcdata(value)
186         return value and tparser.pcdata(tostring(value))
187 end
188
189 --- Strip HTML tags from given string.
190 -- @param value String containing the HTML text
191 -- @return      String with HTML tags stripped of
192 function striptags(value)
193         return value and tparser.striptags(tostring(value))
194 end
195
196 --- Splits given string on a defined separator sequence and return a table
197 -- containing the resulting substrings. The optional max parameter specifies
198 -- the number of bytes to process, regardless of the actual length of the given
199 -- string. The optional last parameter, regex, specifies whether the separator
200 -- sequence is interpreted as regular expression.
201 -- @param str           String value containing the data to split up
202 -- @param pat           String with separator pattern (optional, defaults to "\n")
203 -- @param max           Maximum times to split (optional)
204 -- @param regex         Boolean indicating whether to interpret the separator
205 --                                      pattern as regular expression (optional, default is false)
206 -- @return                      Table containing the resulting substrings
207 function split(str, pat, max, regex)
208         pat = pat or "\n"
209         max = max or #str
210
211         local t = {}
212         local c = 1
213
214         if #str == 0 then
215                 return {""}
216         end
217
218         if #pat == 0 then
219                 return nil
220         end
221
222         if max == 0 then
223                 return str
224         end
225
226         repeat
227                 local s, e = str:find(pat, c, not regex)
228                 max = max - 1
229                 if s and max < 0 then
230                         t[#t+1] = str:sub(c)
231                 else
232                         t[#t+1] = str:sub(c, s and s - 1)
233                 end
234                 c = e and e + 1 or #str + 1
235         until not s or max < 0
236
237         return t
238 end
239
240 --- Remove leading and trailing whitespace from given string value.
241 -- @param str   String value containing whitespace padded data
242 -- @return              String value with leading and trailing space removed
243 function trim(str)
244         return (str:gsub("^%s*(.-)%s*$", "%1"))
245 end
246
247 --- Count the occurences of given substring in given string.
248 -- @param str           String to search in
249 -- @param pattern       String containing pattern to find
250 -- @return                      Number of found occurences
251 function cmatch(str, pat)
252         local count = 0
253         for _ in str:gmatch(pat) do count = count + 1 end
254         return count
255 end
256
257 --- Return a matching iterator for the given value. The iterator will return
258 -- one token per invocation, the tokens are separated by whitespace. If the
259 -- input value is a table, it is transformed into a string first. A nil value
260 -- will result in a valid interator which aborts with the first invocation.
261 -- @param val           The value to scan (table, string or nil)
262 -- @return                      Iterator which returns one token per call
263 function imatch(v)
264         if type(v) == "table" then
265                 local k = nil
266                 return function()
267                         k = next(v, k)
268                         return v[k]
269                 end
270
271         elseif type(v) == "number" or type(v) == "boolean" then
272                 local x = true
273                 return function()
274                         if x then
275                                 x = false
276                                 return tostring(v)
277                         end
278                 end
279
280         elseif type(v) == "userdata" or type(v) == "string" then
281                 return tostring(v):gmatch("%S+")
282         end
283
284         return function() end
285 end
286
287 --- Parse certain units from the given string and return the canonical integer
288 -- value or 0 if the unit is unknown. Upper- or lower case is irrelevant.
289 -- Recognized units are:
290 --      o "y"   - one year   (60*60*24*366)
291 --  o "m"       - one month  (60*60*24*31)
292 --  o "w"       - one week   (60*60*24*7)
293 --  o "d"       - one day    (60*60*24)
294 --  o "h"       - one hour       (60*60)
295 --  o "min"     - one minute (60)
296 --  o "kb"  - one kilobyte (1024)
297 --  o "mb"      - one megabyte (1024*1024)
298 --  o "gb"      - one gigabyte (1024*1024*1024)
299 --  o "kib" - one si kilobyte (1000)
300 --  o "mib"     - one si megabyte (1000*1000)
301 --  o "gib"     - one si gigabyte (1000*1000*1000)
302 -- @param ustr  String containing a numerical value with trailing unit
303 -- @return              Number containing the canonical value
304 function parse_units(ustr)
305
306         local val = 0
307
308         -- unit map
309         local map = {
310                 -- date stuff
311                 y   = 60 * 60 * 24 * 366,
312                 m   = 60 * 60 * 24 * 31,
313                 w   = 60 * 60 * 24 * 7,
314                 d   = 60 * 60 * 24,
315                 h   = 60 * 60,
316                 min = 60,
317
318                 -- storage sizes
319                 kb  = 1024,
320                 mb  = 1024 * 1024,
321                 gb  = 1024 * 1024 * 1024,
322
323                 -- storage sizes (si)
324                 kib = 1000,
325                 mib = 1000 * 1000,
326                 gib = 1000 * 1000 * 1000
327         }
328
329         -- parse input string
330         for spec in ustr:lower():gmatch("[0-9%.]+[a-zA-Z]*") do
331
332                 local num = spec:gsub("[^0-9%.]+$","")
333                 local spn = spec:gsub("^[0-9%.]+", "")
334
335                 if map[spn] or map[spn:sub(1,1)] then
336                         val = val + num * ( map[spn] or map[spn:sub(1,1)] )
337                 else
338                         val = val + num
339                 end
340         end
341
342
343         return val
344 end
345
346 -- also register functions above in the central string class for convenience
347 string.pcdata      = pcdata
348 string.striptags   = striptags
349 string.split       = split
350 string.trim        = trim
351 string.cmatch      = cmatch
352 string.parse_units = parse_units
353
354
355 --- Appends numerically indexed tables or single objects to a given table.
356 -- @param src   Target table
357 -- @param ...   Objects to insert
358 -- @return              Target table
359 function append(src, ...)
360         for i, a in ipairs({...}) do
361                 if type(a) == "table" then
362                         for j, v in ipairs(a) do
363                                 src[#src+1] = v
364                         end
365                 else
366                         src[#src+1] = a
367                 end
368         end
369         return src
370 end
371
372 --- Combines two or more numerically indexed tables and single objects into one table.
373 -- @param tbl1  Table value to combine
374 -- @param tbl2  Table value to combine
375 -- @param ...   More tables to combine
376 -- @return              Table value containing all values of given tables
377 function combine(...)
378         return append({}, ...)
379 end
380
381 --- Checks whether the given table contains the given value.
382 -- @param table Table value
383 -- @param value Value to search within the given table
384 -- @return              Boolean indicating whether the given value occurs within table
385 function contains(table, value)
386         for k, v in pairs(table) do
387                 if value == v then
388                         return k
389                 end
390         end
391         return false
392 end
393
394 --- Update values in given table with the values from the second given table.
395 -- Both table are - in fact - merged together.
396 -- @param t                     Table which should be updated
397 -- @param updates       Table containing the values to update
398 -- @return                      Always nil
399 function update(t, updates)
400         for k, v in pairs(updates) do
401                 t[k] = v
402         end
403 end
404
405 --- Retrieve all keys of given associative table.
406 -- @param t     Table to extract keys from
407 -- @return      Sorted table containing the keys
408 function keys(t)
409         local keys = { }
410         if t then
411                 for k, _ in kspairs(t) do
412                         keys[#keys+1] = k
413                 end
414         end
415         return keys
416 end
417
418 --- Clones the given object and return it's copy.
419 -- @param object        Table value to clone
420 -- @param deep          Boolean indicating whether to do recursive cloning
421 -- @return                      Cloned table value
422 function clone(object, deep)
423         local copy = {}
424
425         for k, v in pairs(object) do
426                 if deep and type(v) == "table" then
427                         v = clone(v, deep)
428                 end
429                 copy[k] = v
430         end
431
432         return setmetatable(copy, getmetatable(object))
433 end
434
435
436 --- Create a dynamic table which automatically creates subtables.
437 -- @return      Dynamic Table
438 function dtable()
439         return setmetatable({}, { __index =
440                 function(tbl, key)
441                         return rawget(tbl, key)
442                          or rawget(rawset(tbl, key, dtable()), key)
443                 end
444         })
445 end
446
447
448 -- Serialize the contents of a table value.
449 function _serialize_table(t, seen)
450         assert(not seen[t], "Recursion detected.")
451         seen[t] = true
452
453         local data  = ""
454         local idata = ""
455         local ilen  = 0
456
457         for k, v in pairs(t) do
458                 if type(k) ~= "number" or k < 1 or math.floor(k) ~= k or ( k - #t ) > 3 then
459                         k = serialize_data(k, seen)
460                         v = serialize_data(v, seen)
461                         data = data .. ( #data > 0 and ", " or "" ) ..
462                                 '[' .. k .. '] = ' .. v
463                 elseif k > ilen then
464                         ilen = k
465                 end
466         end
467
468         for i = 1, ilen do
469                 local v = serialize_data(t[i], seen)
470                 idata = idata .. ( #idata > 0 and ", " or "" ) .. v
471         end
472
473         return idata .. ( #data > 0 and #idata > 0 and ", " or "" ) .. data
474 end
475
476 --- Recursively serialize given data to lua code, suitable for restoring
477 -- with loadstring().
478 -- @param val   Value containing the data to serialize
479 -- @return              String value containing the serialized code
480 -- @see                 restore_data
481 -- @see                 get_bytecode
482 function serialize_data(val, seen)
483         seen = seen or setmetatable({}, {__mode="k"})
484
485         if val == nil then
486                 return "nil"
487         elseif type(val) == "number" then
488                 return val
489         elseif type(val) == "string" then
490                 return "%q" % val
491         elseif type(val) == "boolean" then
492                 return val and "true" or "false"
493         elseif type(val) == "function" then
494                 return "loadstring(%q)" % get_bytecode(val)
495         elseif type(val) == "table" then
496                 return "{ " .. _serialize_table(val, seen) .. " }"
497         else
498                 return '"[unhandled data type:' .. type(val) .. ']"'
499         end
500 end
501
502 --- Restore data previously serialized with serialize_data().
503 -- @param str   String containing the data to restore
504 -- @return              Value containing the restored data structure
505 -- @see                 serialize_data
506 -- @see                 get_bytecode
507 function restore_data(str)
508         return loadstring("return " .. str)()
509 end
510
511
512 --
513 -- Byte code manipulation routines
514 --
515
516 --- Return the current runtime bytecode of the given data. The byte code
517 -- will be stripped before it is returned.
518 -- @param val   Value to return as bytecode
519 -- @return              String value containing the bytecode of the given data
520 function get_bytecode(val)
521         local code
522
523         if type(val) == "function" then
524                 code = string.dump(val)
525         else
526                 code = string.dump( loadstring( "return " .. serialize_data(val) ) )
527         end
528
529         return code -- and strip_bytecode(code)
530 end
531
532 --- Strips unnescessary lua bytecode from given string. Information like line
533 -- numbers and debugging numbers will be discarded. Original version by
534 -- Peter Cawley (http://lua-users.org/lists/lua-l/2008-02/msg01158.html)
535 -- @param code  String value containing the original lua byte code
536 -- @return              String value containing the stripped lua byte code
537 function strip_bytecode(code)
538         local version, format, endian, int, size, ins, num, lnum = code:byte(5, 12)
539         local subint
540         if endian == 1 then
541                 subint = function(code, i, l)
542                         local val = 0
543                         for n = l, 1, -1 do
544                                 val = val * 256 + code:byte(i + n - 1)
545                         end
546                         return val, i + l
547                 end
548         else
549                 subint = function(code, i, l)
550                         local val = 0
551                         for n = 1, l, 1 do
552                                 val = val * 256 + code:byte(i + n - 1)
553                         end
554                         return val, i + l
555                 end
556         end
557
558         local function strip_function(code)
559                 local count, offset = subint(code, 1, size)
560                 local stripped = { string.rep("\0", size) }
561                 local dirty = offset + count
562                 offset = offset + count + int * 2 + 4
563                 offset = offset + int + subint(code, offset, int) * ins
564                 count, offset = subint(code, offset, int)
565                 for n = 1, count do
566                         local t
567                         t, offset = subint(code, offset, 1)
568                         if t == 1 then
569                                 offset = offset + 1
570                         elseif t == 4 then
571                                 offset = offset + size + subint(code, offset, size)
572                         elseif t == 3 then
573                                 offset = offset + num
574                         elseif t == 254 or t == 9 then
575                                 offset = offset + lnum
576                         end
577                 end
578                 count, offset = subint(code, offset, int)
579                 stripped[#stripped+1] = code:sub(dirty, offset - 1)
580                 for n = 1, count do
581                         local proto, off = strip_function(code:sub(offset, -1))
582                         stripped[#stripped+1] = proto
583                         offset = offset + off - 1
584                 end
585                 offset = offset + subint(code, offset, int) * int + int
586                 count, offset = subint(code, offset, int)
587                 for n = 1, count do
588                         offset = offset + subint(code, offset, size) + size + int * 2
589                 end
590                 count, offset = subint(code, offset, int)
591                 for n = 1, count do
592                         offset = offset + subint(code, offset, size) + size
593                 end
594                 stripped[#stripped+1] = string.rep("\0", int * 3)
595                 return table.concat(stripped), offset
596         end
597
598         return code:sub(1,12) .. strip_function(code:sub(13,-1))
599 end
600
601
602 --
603 -- Sorting iterator functions
604 --
605
606 function _sortiter( t, f )
607         local keys = { }
608
609         local k, v
610         for k, v in pairs(t) do
611                 keys[#keys+1] = k
612         end
613
614         local _pos = 0
615
616         table.sort( keys, f )
617
618         return function()
619                 _pos = _pos + 1
620                 if _pos <= #keys then
621                         return keys[_pos], t[keys[_pos]], _pos
622                 end
623         end
624 end
625
626 --- Return a key, value iterator which returns the values sorted according to
627 -- the provided callback function.
628 -- @param t     The table to iterate
629 -- @param f A callback function to decide the order of elements
630 -- @return      Function value containing the corresponding iterator
631 function spairs(t,f)
632         return _sortiter( t, f )
633 end
634
635 --- Return a key, value iterator for the given table.
636 -- The table pairs are sorted by key.
637 -- @param t     The table to iterate
638 -- @return      Function value containing the corresponding iterator
639 function kspairs(t)
640         return _sortiter( t )
641 end
642
643 --- Return a key, value iterator for the given table.
644 -- The table pairs are sorted by value.
645 -- @param t     The table to iterate
646 -- @return      Function value containing the corresponding iterator
647 function vspairs(t)
648         return _sortiter( t, function (a,b) return t[a] < t[b] end )
649 end
650
651
652 --
653 -- System utility functions
654 --
655
656 --- Test whether the current system is operating in big endian mode.
657 -- @return      Boolean value indicating whether system is big endian
658 function bigendian()
659         return string.byte(string.dump(function() end), 7) == 0
660 end
661
662 --- Execute given commandline and gather stdout.
663 -- @param command       String containing command to execute
664 -- @return                      String containing the command's stdout
665 function exec(command)
666         local pp   = io.popen(command)
667         local data = pp:read("*a")
668         pp:close()
669
670         return data
671 end
672
673 --- Return a line-buffered iterator over the output of given command.
674 -- @param command       String containing the command to execute
675 -- @return                      Iterator
676 function execi(command)
677         local pp = io.popen(command)
678
679         return pp and function()
680                 local line = pp:read()
681
682                 if not line then
683                         pp:close()
684                 end
685
686                 return line
687         end
688 end
689
690 -- Deprecated
691 function execl(command)
692         local pp   = io.popen(command)
693         local line = ""
694         local data = {}
695
696         while true do
697                 line = pp:read()
698                 if (line == nil) then break end
699                 data[#data+1] = line
700         end
701         pp:close()
702
703         return data
704 end
705
706 --- Returns the absolute path to LuCI base directory.
707 -- @return              String containing the directory path
708 function libpath()
709         return require "nixio.fs".dirname(ldebug.__file__)
710 end
711
712
713 --
714 -- Coroutine safe xpcall and pcall versions modified for Luci
715 -- original version:
716 -- coxpcall 1.13 - Copyright 2005 - Kepler Project (www.keplerproject.org)
717 --
718 -- Copyright © 2005 Kepler Project.
719 -- Permission is hereby granted, free of charge, to any person obtaining a
720 -- copy of this software and associated documentation files (the "Software"),
721 -- to deal in the Software without restriction, including without limitation
722 -- the rights to use, copy, modify, merge, publish, distribute, sublicense,
723 -- and/or sell copies of the Software, and to permit persons to whom the
724 -- Software is furnished to do so, subject to the following conditions:
725 --
726 -- The above copyright notice and this permission notice shall be
727 -- included in all copies or substantial portions of the Software.
728 --
729 -- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
730 -- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
731 -- OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
732 -- IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
733 -- DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
734 -- TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
735 -- OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
736
737 local performResume, handleReturnValue
738 local oldpcall, oldxpcall = pcall, xpcall
739 coxpt = {}
740 setmetatable(coxpt, {__mode = "kv"})
741
742 -- Identity function for copcall
743 local function copcall_id(trace, ...)
744   return ...
745 end
746
747 --- This is a coroutine-safe drop-in replacement for Lua's "xpcall"-function
748 -- @param f             Lua function to be called protected
749 -- @param err   Custom error handler
750 -- @param ...   Parameters passed to the function
751 -- @return              A boolean whether the function call succeeded and the return
752 --                              values of either the function or the error handler
753 function coxpcall(f, err, ...)
754         local res, co = oldpcall(coroutine.create, f)
755         if not res then
756                 local params = {...}
757                 local newf = function() return f(unpack(params)) end
758                 co = coroutine.create(newf)
759         end
760         local c = coroutine.running()
761         coxpt[co] = coxpt[c] or c or 0
762
763         return performResume(err, co, ...)
764 end
765
766 --- This is a coroutine-safe drop-in replacement for Lua's "pcall"-function
767 -- @param f             Lua function to be called protected
768 -- @param ...   Parameters passed to the function
769 -- @return              A boolean whether the function call succeeded and the returns
770 --                              values of the function or the error object
771 function copcall(f, ...)
772         return coxpcall(f, copcall_id, ...)
773 end
774
775 -- Handle return value of protected call
776 function handleReturnValue(err, co, status, ...)
777         if not status then
778                 return false, err(debug.traceback(co, (...)), ...)
779         end
780
781         if coroutine.status(co) ~= 'suspended' then
782                 return true, ...
783         end
784
785         return performResume(err, co, coroutine.yield(...))
786 end
787
788 -- Resume execution of protected function call
789 function performResume(err, co, ...)
790         return handleReturnValue(err, co, coroutine.resume(co, ...))
791 end