mware/readline.c

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   6  * Bertos is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  * As a special exception, you may use this file as part of a free software
  21  * library without restriction.  Specifically, if other files instantiate
  22  * templates or use macros or inline functions from this file, or you compile
  23  * this file and link it with other files to produce an executable, this
  24  * file does not by itself cause the resulting executable to be covered by
  25  * the GNU General Public License.  This exception does not however
  26  * invalidate any other reasons why the executable file might be covered by
  27  * the GNU General Public License.
  28  *
  29  * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
  30  * Copyright 2004 Giovanni Bajo
  31  * All Rights Reserved.
  32  * -->
  33  *
  34  * \brief Line editing support with history
  35  *
  36  * Rationale for basic implementation choices:
  37  *
  38  * \li The history is implemented storing consecutive ASCIIZ strings within an array of memory. When
  39  * the history is full, the first (oldest) line is cancelled and the whole buffer is memmoved to
  40  * overwrite it and make room. while this is is obviously not the fastest algorithm (which would
  41  * require the use of a circular buffer) it is surely good enough for this module, which does not
  42  * aim at fast performances (line editing does not require to be blazingly fast).
  43  *
  44  * \li The first character in the history is always \c \\0, and it is used as a guard. By 'wasting' it
  45  * in this way, the code actually gets much simpler in that we remove many checks when moving
  46  * backward (\c i>0 and similar).
  47  *
  48  * \li While editing, the current index points to the position of the buffer which contains the
  49  * last character typed in (exactly like a stack pointer). This also allows to simplify calculations
  50  * and to make easier using the last byte of history.
  51  *
  52  * \li While editing, the current line is always kept null-terminated. This is important because
  53  * if the user press ENTER, we must have room to add a \c \\0 to terminate the line. If the line
  54  * is as long as the whole history buffer, there would not be space for it. By always keeping the
  55  * \c \\0 at the end, we properly ensure this without making index checks harder.
  56  *
  57  * \li When removing a line from the history (see \c pop_history()), instead of updating all the
  58  * indices we have around, we move backward the pointer to the history we use. This way, we don't
  59  * have to update anything. This means that we keep two pointers to the history: \c real_history
  60  * always points to the physical start, while \c history is the adjusted pointer (that is
  61  * dereference to read/write to it).
  62  *
  63  * \todo Use up/down to move through history  The history line will be copied to the current line,
  64  * making sure there is room for it.
  65  *
  66  * \version $Id$
  67  *
  68  * \author Giovanni Bajo <rasky@develer.com>
  69  */
  70
  71
  72 #include "readline.h"
  73
  74 #include <cfg/compiler.h>
  75 #include <cfg/debug.h>
  76
  77 #include <stdio.h>
  78 #include <drv/ser.h>
  79
  80
  81 /// Enable compilation of the unit test code
  82 #define DEBUG_UNIT_TEST       0
  83
  84 /// Enable dump of the history after each line
  85 #define DEBUG_DUMP_HISTORY    0
  86
  87
  88 /** Special keys (escape sequences converted to a single code) */
  89 enum RL_KEYS {
  90         SPECIAL_KEYS = 0x1000,
  91
  92         /*
  93          * Three byte keys:
  94          * #################
  95          * UpArrow:     0x1B 0x5B 0X41
  96          * DownArrow:   0x1B 0x5B 0X42
  97          * RightArrow:  0x1B 0x5B 0x43
  98          * LeftArrow:   0x1b 0x5B 0x44
  99          * Beak(Pause): 0x1b 0x5B 0x50
 100         */
 101         KEY_UP_ARROW,
 102         KEY_DOWN_ARROW,
 103         KEY_LEFT_ARROW,
 104         KEY_RIGHT_ARROW,
 105         KEY_PAUSE,
 106
 107         /*
 108          * Four byte keys:
 109          * ################
 110          * F1:          0x1b 0x5B 0x5B 0x41
 111          * F2:          0x1b 0x5B 0x5B 0x42
 112          * F3:          0x1b 0x5B 0x5B 0x43
 113          * F4:          0x1b 0x5B 0x5B 0x44
 114          * F5:          0x1b 0x5B 0x5B 0x45
 115          * Ins:         0x1b 0x5B 0x32 0x7E
 116          * Home:        0x1b 0x5B 0x31 0x7E
 117          * PgUp:        0x1b 0x5B 0x35 0x7E
 118          * Del:         0x1b 0x5B 0x33 0x7E
 119          * End:         0x1b 0x5B 0x34 0x7E
 120          * PgDn:        0x1b 0x5B 0x36 0x7E
 121          */
 122         KEY_F1, KEY_F2, KEY_F3, KEY_F4, KEY_F5,
 123         KEY_INS, KEY_HOME, KEY_PGUP, KEY_DEL, KEY_END, KEY_PGDN,
 124
 125         /*
 126          * Five byte keys:
 127          * ################
 128          * F6:          0x1b 0x5B 0x31 0x37 0x7E
 129          * F7:          0x1b 0x5B 0x31 0x38 0x7E
 130          * F8:          0x1b 0x5B 0x31 0x39 0x7E
 131          * F9:          0x1b 0x5B 0x32 0x30 0x7E
 132          * F10:         0x1b 0x5B 0x32 0x31 0x7E
 133          * F11:         0x1b 0x5B 0x32 0x33 0x7E
 134          * F12:         0x1b 0x5B 0x32 0x34 0x7E
 135          */
 136         KEY_F6, KEY_F7, KEY_F8, KEY_F9,
 137         KEY_F10, KEY_F11, KEY_F12,
 138 };
 139
 140 /** Check if \a c is a separator between words.
 141  *  \note Parameter \a c is evaluated multiple times
 142  */
 143 #define IS_WORD_SEPARATOR(c) ((c) == ' ' || (c) == '\0')
 144
 145 /// Write the string \a txt to the IO output (without any kind of termination)
 146 INLINE void rl_puts(const struct RLContext* ctx, const char* txt)
 147 {
 148         if (!ctx->put)
 149                 return;
 150
 151         while (*txt)
 152                 ctx->put(*txt++, ctx->put_param);
 153 }
 154
 155 /// Write character \a ch to the IO output.
 156 INLINE void rl_putc(const struct RLContext* ctx, char ch)
 157 {
 158         if (ctx->put)
 159                 ctx->put(ch, ctx->put_param);
 160 }
 161
 162 /** Read a character from the IO into \a ch. This function also takes
 163  *  care of converting the ANSI escape sequences into one of the codes
 164  *  defined in \c RL_KEYS.
 165  */
 166 static bool rl_getc(const struct RLContext* ctx, int* ch)
 167 {
 168         int c = ctx->get(ctx->get_param);
 169
 170         if (c == EOF)
 171         {
 172                 if (ctx->clear)
 173                         ctx->clear(ctx->clear_param);
 174
 175                 return false;
 176         }
 177
 178         if (c == 0x1B)
 179         {
 180                 // Unknown ESC sequence. Ignore it and read
 181                 //  return next character.
 182                 if (ctx->get(ctx->get_param) != 0x5B)
 183                         return rl_getc(ctx, ch);
 184
 185                 /* To be added:
 186                         * Home:        0x1b 0x5B 0x31 0x7E
 187                         * F6:          0x1b 0x5B 0x31 0x37 0x7E
 188                         * F7:          0x1b 0x5B 0x31 0x38 0x7E
 189                         * F8:          0x1b 0x5B 0x31 0x39 0x7E
 190                         * Ins:         0x1b 0x5B 0x32 0x7E
 191                         * F9:          0x1b 0x5B 0x32 0x30 0x7E
 192                         * F10:         0x1b 0x5B 0x32 0x31 0x7E
 193                         * F11:         0x1b 0x5B 0x32 0x33 0x7E
 194                         * F12:         0x1b 0x5B 0x32 0x34 0x7E
 195                         * Del:         0x1b 0x5B 0x33 0x7E
 196                         * End:         0x1b 0x5B 0x34 0x7E
 197                         * PgUp:        0x1b 0x5B 0x35 0x7E
 198                         * PgDn:        0x1b 0x5B 0x36 0x7E
 199                 */
 200
 201                 c = ctx->get(ctx->get_param);
 202                 switch (c)
 203                 {
 204                 case 0x41: c = KEY_UP_ARROW; break;
 205                 case 0x42: c = KEY_DOWN_ARROW; break;
 206                 case 0x43: c = KEY_RIGHT_ARROW; break;
 207                 case 0x44: c = KEY_LEFT_ARROW; break;
 208                 case 0x50: c = KEY_PAUSE; break;
 209                 case 0x5B:
 210                         c = ctx->get(ctx->get_param);
 211                         switch (c)
 212                         {
 213                         case 0x41: c = KEY_F1; break;
 214                         case 0x42: c = KEY_F2; break;
 215                         case 0x43: c = KEY_F3; break;
 216                         case 0x44: c = KEY_F4; break;
 217                         case 0x45: c = KEY_F5; break;
 218                         default: return rl_getc(ctx, ch);
 219                         }
 220                         break;
 221                 default: return rl_getc(ctx, ch);
 222                 }
 223         }
 224
 225         *ch = c;
 226         return true;
 227 }
 228
 229 INLINE void beep(struct RLContext* ctx)
 230 {
 231         rl_putc(ctx, '\a');
 232 }
 233
 234 static bool pop_history(struct RLContext* ctx, int total_len)
 235 {
 236         // Compute the length of the first command (including terminator).
 237         int len = strlen(ctx->real_history+1)+1;
 238
 239         // (the first byte of the history should always be 0)
 240         ASSERT(ctx->real_history[0] == '\0');
 241
 242         // If it is the only one in the history, do nothing
 243         if (len == total_len)
 244                 return false;
 245
 246         // Overwrite the first command with the second one
 247         memmove(ctx->real_history, ctx->real_history+len, HISTORY_SIZE-len);
 248
 249         // Move back the ctx->buffer pointer so that all the indices are still valid
 250         ctx->history -= len;
 251
 252         return true;
 253 }
 254
 255 /// Check if index \a i points to the begin of the history.
 256 INLINE bool is_history_begin(struct RLContext* ctx, int i)
 257 { return ctx->history + i == ctx->real_history; }
 258
 259 /// Check if index \a i points to the (exclusive) end of history
 260 INLINE bool is_history_end(struct RLContext* ctx, int i)
 261 { return ctx->history + i == ctx->real_history + HISTORY_SIZE; }
 262
 263 /// Check if index \a i points to the (exclusive) end of history, or somewhere past the end.
 264 INLINE bool is_history_past_end(struct RLContext* ctx, int i)
 265 { return ctx->history + i >= ctx->real_history + HISTORY_SIZE; }
 266
 267 /** Insert \a num_chars characters from \a ch into the history buffer at the
 268  *  position indicated by \a curpos. If needed, remove old history to make room.
 269  *  Returns true if everything was successful, false if there was no room to
 270  *  add the characters.
 271  *  \note \a num_chars can be 0, in which case we just make sure the line is
 272  *  correctly zero-terminated (ASCIIZ format).
 273  */
 274 static bool insert_chars(struct RLContext* ctx, size_t *curpos, const char* ch, int num_chars)
 275 {
 276         ASSERT(!is_history_past_end(ctx, *curpos));
 277
 278         while (is_history_past_end(ctx, *curpos+num_chars+1))
 279         {
 280                 if (!pop_history(ctx, *curpos))
 281                         return false;
 282         }
 283
 284         while (num_chars--)
 285                 ctx->history[++(*curpos)] = *ch++;
 286
 287         ASSERT(!is_history_past_end(ctx, *curpos + 1));
 288         ctx->history[*curpos+1] = '\0';
 289         return true;
 290 }
 291
 292 /// Insert a single character \a ch into the buffer (with the same semantic of \c insert_chars())
 293 static bool insert_char(struct RLContext* ctx, size_t *curpos, char ch)
 294 {
 295         return insert_chars(ctx, curpos, &ch, 1);
 296 }
 297
 298 #if DEBUG_DUMP_HISTORY
 299 /// Dump the internal history of a context (used only for debug purposes)
 300 static void dump_history(struct RLContext* ctx)
 301 {
 302         int k;
 303         char buf[8];
 304         ASSERT(ctx->real_history[0] == '\0');
 305         rl_puts(ctx, "History dump:");
 306         rl_puts(ctx, "\r\n");
 307         for (k = 1;
 308              ctx->real_history + k != ctx->history + ctx->history_pos + 1;
 309              k += strlen(&ctx->real_history[k]) + 1)
 310         {
 311                 rl_puts(ctx, &ctx->real_history[k]);
 312                 rl_puts(ctx, "\r\n");
 313         }
 314
 315         sprintf(buf, "%d\r\n", ctx->history_pos + (ctx->history - ctx->real_history));
 316         rl_puts(ctx, buf);
 317 }
 318 #endif /* DEBUG_DUMP_HISTORY */
 319
 320 /// Complete the current word. Return false if no unambiguous completion was found
 321 static bool complete_word(struct RLContext *ctx, size_t *curpos)
 322 {
 323         const char* completed_word;
 324         size_t wstart;
 325
 326         // If the current character is a separator,
 327         //  there is nothing to complete
 328         wstart = *curpos;
 329         if (IS_WORD_SEPARATOR(ctx->history[wstart]))
 330         {
 331                 beep(ctx);
 332                 return false;
 333         }
 334
 335         // Find the separator before the current word
 336         do
 337                 --wstart;
 338         while (!IS_WORD_SEPARATOR(ctx->history[wstart]));
 339
 340         // Complete the word through the hook
 341         completed_word = ctx->match(ctx->match_param, ctx->history + wstart + 1, *curpos - wstart);
 342         if (!completed_word)
 343                 return false;
 344
 345         // Move back the terminal cursor to the separator
 346         while (*curpos != wstart)
 347         {
 348                 rl_putc(ctx, '\b');
 349                 --*curpos;
 350         }
 351
 352         // Insert the completed command
 353         insert_chars(ctx, curpos, completed_word, strlen(completed_word));
 354         rl_puts(ctx, completed_word);
 355         insert_char(ctx, curpos, ' ');
 356         rl_putc(ctx, ' ');
 357
 358         return true;
 359 }
 360
 361 void rl_refresh(struct RLContext* ctx)
 362 {
 363         rl_puts(ctx, "\r\n");
 364         if (ctx->prompt)
 365                 rl_puts(ctx, ctx->prompt);
 366         rl_puts(ctx, ctx->history + ctx->history_pos + 1);
 367 }
 368
 369 const char* rl_readline(struct RLContext* ctx)
 370 {
 371         size_t i = ctx->history_pos;
 372
 373         if (ctx->prompt)
 374                 rl_puts(ctx, ctx->prompt);
 375
 376         insert_chars(ctx, &i, NULL, 0);
 377
 378         while (1)
 379         {
 380                 char ch;
 381                 int c;
 382
 383                 ASSERT(ctx->history - ctx->real_history + ctx->line_pos < HISTORY_SIZE);
 384
 385                 if (!rl_getc(ctx, &c))
 386                         return NULL;
 387
 388                 // Just ignore special keys for now
 389                 if (c > SPECIAL_KEYS)
 390                         continue;
 391
 392                 if (c == '\t')
 393                 {
 394                         // Ask the match hook if available
 395                         if (!ctx->match)
 396                                 return false;
 397
 398                         complete_word(ctx, &ctx->line_pos);
 399                         continue;
 400                 }
 401
 402                 if (c == '\r' || c == '\n')
 403                 {
 404                         if (ctx->prompt)
 405                                 rl_puts(ctx, ctx->prompt);
 406
 407                         // Terminate line
 408                         insert_chars(ctx, &ctx->line_pos, NULL, 0);
 409                         rl_puts(ctx, "\r\n");
 410                         break;
 411                 }
 412
 413                 // Backspace cancels a character, or it is ignored if at
 414                 //  the start of the line
 415                 if (c == '\b')
 416                 {
 417                         if (ctx->history[ctx->line_pos] != '\0')
 418                         {
 419                                 --ctx->line_pos;
 420                                 rl_puts(ctx, "\b \b");
 421                         }
 422                         continue;
 423                 }
 424
 425                 // Add a character to the buffer, if possible
 426                 ch = (char)c;
 427                 ASSERT2(ch == c, "a special key was not properly handled");
 428                 if (insert_chars(ctx, &ctx->line_pos, &ch, 1))
 429                 {
 430                         rl_putc(ctx, ch);
 431                 }
 432                 else
 433                 {
 434                         beep(ctx);
 435                 }
 436         }
 437
 438         ctx->history_pos = ctx->line_pos + 1;
 439         while (ctx->history[ctx->line_pos] != '\0')
 440                 --ctx->line_pos;
 441
 442         // Do not store empty lines in the history
 443         if (ctx->line_pos == ctx->history_pos - 1)
 444                 ctx->history_pos -= 1;
 445
 446 #if DEBUG_DUMP_HISTORY
 447         dump_history(ctx);
 448 #endif
 449
 450         // Since the current pointer now points to the separator, we need
 451         //  to return the first character
 452         return &ctx->history[ctx->line_pos + 1];
 453 }
 454
 455
 456 #if DEBUG_UNIT_TEST
 457
 458 /** Perform the unit test for the readline library */
 459 void rl_test(void);
 460
 461 #if HISTORY_SIZE != 32
 462         #error This test needs HISTORY_SIZE to be set at 32
 463 #endif
 464
 465 static struct RLContext test_ctx;
 466
 467 static char* test_getc_ptr;
 468 static int test_getc(void* data)
 469 {
 470         return *test_getc_ptr++;
 471 }
 472
 473 /** Perform a readline test. The function pipes the characters from \a input_buffer
 474  *  through the I/O to \c rl_readline(). After the whole string is sent, \c do_test()
 475  *  checks if the current history within the context match \a expected_history.
 476  */
 477 static bool do_test(char* input_buffer, char* expected_history)
 478 {
 479         rl_init_ctx(&test_ctx);
 480         rl_sethook_get(&test_ctx, test_getc, NULL);
 481
 482         test_getc_ptr = input_buffer;
 483         while (*test_getc_ptr)
 484                 rl_readline(&test_ctx);
 485
 486         if (memcmp(test_ctx.real_history, expected_history, HISTORY_SIZE) != 0)
 487         {
 488                 ASSERT2(0, "history compare failed");
 489                 return false;
 490         }
 491
 492         return true;
 493 }
 494
 495 void rl_test(void)
 496 {
 497         char* test1_in = "a\nb\nc\nd\ne\nf\ng\nh\ni\nj\nk\nl\nm\nn\no\np\nq\nr\ns\nt\nu\nv\nw\nx\ny\nz\n";
 498         char test1_hist[HISTORY_SIZE] = "\0l\0m\0n\0o\0p\0q\0r\0s\0t\0u\0v\0w\0x\0y\0z";
 499
 500         if (!do_test(test1_in, test1_hist))
 501                 return;
 502
 503         kprintf("rl_test successful\n");
 504 }
 505
 506 #endif /* DEBUG_UNIT_TEST */
 507