Implement Damerau Levenshtein distance checking for parts and memories

[MCUdude]

1593 related

Right before the v7.3 release, we added DL distance checking to programmers, so that Avrdude would suggest a programmer in case of a typo, rather than printing the entire list:

$ avrdude -cstk500_pp -patmega48
avrdude error: cannot find programmer id stk500_pp
similar programmer names:
  stk500pp = Atmel STK500 v2 in parallel programming mode
  stk600pp = Atmel STK600 in parallel programming mode
use -c? to see all possible programmers

Neat! Now this would be just as neat to have for memories and parts as well:

$ avrdude -cdryrun -patmega48 -Uflahs:r:-:i
avrdude error: unknown memory flahs

avrdude done.  Thank you.

$ avrdude -cdryrun -patmeag48

avrdude error: AVR part atmeag48 not found

Valid parts are:
  uc3a0512   = AT32UC3A0512
  89S51      = AT89S51
  89S52      = AT89S52
 [...]
  m644rfr2   = ATmega644RFR2
  m645       = ATmega645
  m6450      = ATmega6450
  m6450a     = ATmega6450A
  m6450p     = ATmega6450P
  m645a      = ATmega645A
  m645p      = ATmega645P
  [...]
  avr8ea28   = AVR8EA28
  avr8ea32   = AVR8EA32
  ucr2       = deprecated, use 'uc3a0512'
  lgt8f168p  = LGT8F168P
  lgt8f328p  = LGT8F328P
  lgt8f88p   = LGT8F88P

avrdude done.  Thank you.

One thing that's great about the DL implementation for the programmers is that it won't suggest a programmer that's not compatible with the part:

$ ./avrdude -cstk500hvs -patmega48 # stk500hvsp is the closest match, but not compatible
avrdude error: cannot find programmer id stk500hvs
similar programmer name:
  stk500v2 = Atmel STK500 version 2.x firmware
use -c? to see all possible programmers

But what should we print if:

• Both the part and the programmer doesn't exist/has a typo?
• Only the part has a typo? Suggest only chips that are compatible with the programmer, or the chip names that are close to what the user typed?

[stefanrueger]

There are subtle but important differences between programmer, part and memory names:

• Programmer names are arbitrary product names, sometimes modified by the AVRDUDE project; it makes sense to get help for typos
• Part names are the official ones; small changes, even a letter, can make a big difference for programming, eg, the fuse bitfields between the ATmega328P and ATmega328PB are different. It is unclear to me whether DL can help the user. They really have to get the right part that's in front of them. But if it's implemented it is a bit more involved than for the programmer: the part id, their official part name, any of the full variant part names or their initial part up to a dash can be used to address a part; for example, we have

   m16        = ATmega16
     - ATmega16:       N/A,    Fmax=16 MHz, T=[N/A,    N/A], Vcc=[N/A,     N/A]
     - ATmega16-16AQR: TQFP44, Fmax=16 MHz, T=[N/A,    N/A], Vcc=[4.5 V, 5.5 V]
     - ATmega16-16AU:  TQFP44, Fmax=16 MHz, T=[-40 C, 85 C], Vcc=[4.5 V, 5.5 V]
     - ATmega16-16AUR: TQFP44, Fmax=16 MHz, T=[-40 C, 85 C], Vcc=[4.5 V, 5.5 V]
     - ATmega16-16MQ:  MLF44,  Fmax=16 MHz, T=[-40 C, 85 C], Vcc=[4.5 V, 5.5 V]
     - ATmega16-16MU:  MLF44,  Fmax=16 MHz, T=[-40 C, 85 C], Vcc=[4.5 V, 5.5 V]
     - ATmega16-16MUR: MLF44,  Fmax=16 MHz, T=[-40 C, 85 C], Vcc=[4.5 V, 5.5 V]
     - ATmega16-16PU:  PDIP40, Fmax=16 MHz, T=[-40 C, 85 C], Vcc=[4.5 V, 5.5 V]
     - ATmega16L-8AQ:  TQFP44, Fmax=8 MHz,  T=[-40 C, 85 C], Vcc=[2.7 V, 5.5 V]
     - ATmega16L-8AQR: TQFP44, Fmax=8 MHz,  T=[N/A,    N/A], Vcc=[2.7 V, 5.5 V]
     - ATmega16L-8AU:  TQFP44, Fmax=8 MHz,  T=[-40 C, 85 C], Vcc=[2.7 V, 5.5 V]
     - ATmega16L-8AUR: TQFP44, Fmax=8 MHz,  T=[N/A,    N/A], Vcc=[2.7 V, 5.5 V]
     - ATmega16L-8MU:  MLF44,  Fmax=8 MHz,  T=[-40 C, 85 C], Vcc=[2.7 V, 5.5 V]
     - ATmega16L-8MUR: VQFN44, Fmax=8 MHz,  T=[N/A,    N/A], Vcc=[2.7 V, 5.5 V]
     - ATmega16L-8PU:  PDIP40, Fmax=8 MHz,  T=[-40 C, 85 C], Vcc=[2.7 V, 5.5 V]

  In this example one can use m16, ATmega16, ATmega16L and 14 full variant names such as ATmega16-16MU that all point to the same part m16. If a user types ATmega16-16MV, should the user be advised to use ATmega16-16MU, ATmega16-16MQ, and other variants? Probably best to suggest just one entry ATmega16 (m16). If the user types t16 should they be advised of just other ids m16, t11, t12, t13, t15? Probably better to suggest full names, too as in ATmega16 (m16), ATtiny11 (t11), ...

• Memory names can be abbreviated as long as they are unique for the part: flash, flas, fla and fl will work. What should be suggested for fls? Always the full name flash or the closest abbreviations?
• Memory names are matched case sensitive, but programmer and part names are treated case insensitive. DL will be implemented for case insensitive matches (which is probably what you want)

I think it's OK to limit suggestions for a part if the programmer has unambiguously been specified and hence the supported programming interfaces are known.

[MCUdude]

Part names are the official ones; small changes, even a letter, can make a big difference for programming, eg, the fuse bitfields between the ATmega328P and ATmega328PB are different. It is unclear to me whether DL can help the user. They really have to get the right part that's in front of them

OK, this might be more difficult to solve than I first imagined. I'd think that we should only suggest the full name (atmega328p, not m328p), and ignore subtypes (ATmega328P-AU). So if the user uses -c m328L or ATmega328P-AY, suggest atmega328p as the most possible option, not m328p.

Memory names can be abbreviated as long as they are unique for the part: flash, flas, fla and fl will work

I think we should always suggest the full memory name to prevent confusion.

Memory names are matched case sensitive, but programmer and part names are treated case insensitive. DL will be implemented for case-insensitive matches (which is probably what you want)

I think case-insensitive matches for memories would be the best. A user may write -U EEPROM:w:data.hex:i, because EEPROM is usually written with capital letters. However, suggestions would always be that the actual memory name is in avrdude.conf is; eeprom in lover case.

Off topic: Avrdude supports m328p, t817 and x128a1u. Would it be possible to implement support for 128da32 as well?

[stefanrueger]

Avrdude supports m328p, t817 and x128a1u. Would it be possible to implement support for 128da32 as well?

As in PR #1703?

[mcuee]

Off topic: Avrdude supports m328p, t817 and x128a1u. Would it be possible to implement support for 128da32 as well?

Good idea.

[mcuee]

Avrdude supports m328p, t817 and x128a1u. Would it be possible to implement support for 128da32 as well?

As in PR #1703?

PR #1703 looks good.

[stefanrueger]

@MCUdude I won't be attempting to extend Damerau-Levenshtein to parts, mainly because I think that's waaay too complex a task with too little benefit. The asymmetry between parts and programmers as outlined above is just too big...