mware/readline.c

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