def chop(cascade, font_size, string, max_width):
    """Cut `string` into a left half that fits within max_width,
    and a possibly empty right half that didn't."""
    # Half-open interval for cut point: a:b.  len(string) is valid
    # (and most common!) cut point, thus b is initially len(string)+1.
    a, b = 0, len(string)+1
    while a < b - 1:
        c = a + (b - a) // 2
        if cascade.width(string[:c], font_size) <= max_width:
            a = c
        else:
            b = c

    return string[:a], string[a:]