maptable.cc #1

/*
 * Copyright 1995, 1996 Perforce Software.  All rights reserved.
 *
 * This file is part of Perforce - the FAST SCM System.
 */

//
// mapping.cc - the mapping master
//

# include <stdhdrs.h>
# include <ctype.h>
# include <error.h>
# include <strbuf.h>
# include <vararray.h>

# include <debug.h>
# include <tunable.h>
# include <msgdb.h>

# include "maphalf.h"
# include "maptable.h"
# include "mapstring.h"
# include "mapdebug.h"
# include "mapitem.h"

//
// CHARHASH - see diff sequencer for comments
//
# define CHARHASH( h, c ) ( 293 * (h) + (c) )

MapTable::MapTable()
{
	count = 0;
        entry = 0;
	hasMaps = 0;
	hasOverlays = 0;
	hasHavemaps = 0;
	emptyReason = 0;
	joinError = 0;

	trees = new MapTree[2];
}

MapTable::~MapTable()
{
	Clear();
	delete []trees;
}

MapTable &
MapTable::operator=( MapTable &f )
{
        if( this == &f ) 
            return ( *this );

        Clear();
        Insert( &f, 1, 0 );

        return ( *this );
}



void
MapTable::Clear() 
{
        MapItem *map;

        for( map = entry; map; )
        {
            MapItem *next = map->Next();
            delete map;
            map = next;
        }

	count = 0;
	entry = 0;
	hasMaps = 0;
	hasOverlays = 0;
	hasHavemaps = 0;

	trees[ LHS ].Clear();
	trees[ RHS ].Clear();
}

void
MapTable::Reverse()
{
	entry = entry->Reverse();
}

void
MapTable::Insert( MapTable *table, int fwd, int rev )
{
	MapItem *map;

	for( map = table->entry; map; map = map->Next() )
	{
	    if( fwd ) Insert( *map->Lhs(), *map->Rhs(), map->Flag() );
	    if( rev ) Insert( *map->Rhs(), *map->Lhs(), map->Flag() );
	}

	Reverse();
}

void
MapTable::Insert( const StrPtr &lhs, const StrPtr &rhs, MapFlag mapFlag )
{
        entry = new MapItem( entry, lhs, rhs, mapFlag, count++ );

	// For IsEmpty(), HasOverlays() and HasHavemaps()

	if( mapFlag != MfUnmap )
	    hasMaps = 1;

	if( mapFlag == MfRemap || mapFlag == MfHavemap )
	    hasOverlays = 1;
	    
	if( mapFlag == MfHavemap )
	    hasHavemaps = 1;
}

void
MapTable::InsertNoDups( 
	const StrPtr &lhs,
	const StrPtr &rhs,
	MapFlag mapFlag )
{
	// Try to suppress duplicate mappings.

	// Would be nice if Insert() took MapHalfs, rather
	// than starting with the StrPtr again.

	MapHalf hLhs( lhs );
	MapHalf hRhs( rhs );

	// We only look back so far, because big maps cost a 
	// lot to generate, as well.

	int max = 8;

	for( MapItem *map = entry; map && max--; map = map->Next() )
	{
	    if( mapFlag == MfRemap   || map->mapFlag == MfRemap ||
	        mapFlag == MfHavemap || map->mapFlag == MfHavemap )
	    {
	        // Remap and havemaps are additive, so we can
	        // only eliminate literal duplicates.

		if( *map->Lhs() == lhs && *map->Rhs() == rhs )
		    return;
	    }
	    else
	    {
	        // Regular maps have precedence, and so earlier map entries 
	        // mask later additions.  We used to just check for duplicates, 
	        // but MapHalf::Match( MapHalf ) allows us to check for 
	        // superceding maps.  This limits wildcard expansion of maps 
	        // significantly.

		if( map->Lhs()->Match( hLhs ) && map->Rhs()->Match( hRhs ) )
		   return;
	    }
	}

	Insert( lhs, rhs, mapFlag );
}

void
MapTable::Validate( const StrPtr &lhs, const StrPtr &rhs, Error *e )
{
	MapHalf l, r;

	l = lhs;
	r = rhs;

	l.Validate( &r, e );
}

void
MapTable::ValidHalf( MapTableT dir, Error *e )
{
	MapItem *map;

	for( map = entry; map; map = map->Next() )
	    map->Ths( dir )->Validate( 0, e );
}

int
MapTable::GetHash()
{
	unsigned int h = 0;
	MapItem *map;
	char *c;
	int i;

	for( map = entry; map; map = map->Next() )
	{
	    c = map->Lhs()->Text(); 
	    for( i = 0; i < map->Lhs()->Length(); ++i )
	        h = CHARHASH( h, *c++ );
	    c = map->Rhs()->Text(); 
	    for( i = 0; i < map->Rhs()->Length(); ++i )
	        h = CHARHASH( h, *c++ );
	    h = CHARHASH( h, map->Flag() );
	}

	return h;
}

void
MapTable::Dump( const char *trace, int fmt )
{
	MapItem *map;

	p4debug.printf( "map %s: %d items, joinError %d, emptyReason %d\n", 
		trace, count, joinError,
		(emptyReason == 0 ? 0 : emptyReason->SubCode()) );

	if( fmt == 0 )
	{
	  // dump in precedence order (most significant first)
	    for( map = entry; map; map = map->Next() )
	        p4debug.printf( "\t%c %s -> %s\n", 
			" -+$"[ map->Flag() ],
			map->Lhs()->Text(), 
			map->Rhs()->Text() );
	}
	else
	{
	    // dump in the order of a client view 
	    for( int i = Count() - 1; i >= 0; i--)
	        p4debug.printf( "\t%c %s -> %s\n",
			" -+$      123456789"[ GetFlag( Get( i )) ],
			Get( i )->Lhs()->Text( ), 
			Get( i )->Rhs()->Text( ) );
	}
}

int
MapTable::IsSingle() const
{
	// There may be more than one valid mapping: we only look at the
	// highest precendence one, and it must have no widcards.
	// In theory, the check of the rhs is redundant: views are supposed
	// to have matching wildcards.  In theory, there is no difference
	// between theory and practice.  But in practice there is.

	return count >= 1 && !entry->Lhs()->IsWild() && !entry->Rhs()->IsWild();
}

//
// Sort for MakeTree, Strings
//
// Sort produces a MapItem * array, with the MapItem *'s in sorted order.
//
// Put higher precedent maps first -- this helps MapItem::Match().
//

// Needed for MVS.
// See: http://publib.boulder.ibm.com/infocenter/zos/v1r9/index.jsp?topic=/com.ibm.zos.r9.bpxbd00/qsort.htm
//
extern "C"
{
	
static int
sortcmplhs( const void *a1, const void *a2 )
{
	MapItem **e1 = (MapItem **)a1;
	MapItem **e2 = (MapItem **)a2;

	int r = (*e1)->Lhs()->Compare( *(*e2)->Lhs() );

	return r ? r : (*e2)->Slot() - (*e1)->Slot();
}

static int
sortcmprhs( const void *a1, const void *a2 )
{
	MapItem **e1 = (MapItem **)a1;
	MapItem **e2 = (MapItem **)a2;

	int r = (*e1)->Rhs()->Compare( *(*e2)->Rhs() );

	return r ? r : (*e2)->Slot() - (*e1)->Slot();
}


static int
sortcmpstreamslhs( const void *a1, const void *a2 )
{
        int c1, c2;
	MapItem **e1 = (MapItem **)a1;
	MapItem **e2 = (MapItem **)a2;
	char *str1 = (*e1)->Lhs()->Text();
	char *str2 = (*e2)->Lhs()->Text();
	
	int i = 0;
	int j = 0;

	// skip type values on the start of the RHS
	if( ( c1 = str1[ 0 ] ) == '%' || isdigit( c1 ) )
	{
	    while( ( c1 = str1[ i ] ) != '/' )
	        i++;
	}
	if( ( c2 = str2[ 0 ] ) == '%' || isdigit( c2 ) )
	{
	    while( ( c2 = str2[ j ] ) != '/' )
	        j++;
	}

	for( ; ( c1=str1[ i ] ) && ( c2=str2[ j ] ); i++, j++ )
	{
	    if( c1 == c2 )
	        continue;

	    if( 0 == strcmp( &str1[ i ], "...") )
	        return( -1 );

	    if( 0 == strcmp( &str2[ j ], "...") )
	        return( 1 );

	    if( c1 == '*' )
	        return( -1 );

	    if( c2 == '*' )
	        return( 1 );

	    if( c1 == '/' )
	        return( 1 );

	    if( c2 == '/' )
	        return( -1 );

	    // starting with 2013.1, this becomes non-default behavior.

	    if( p4tunable.Get( P4TUNE_STREAMVIEW_DOTS_LOW ) )
	    {
	    // make '.' lower than anything else
	    if( c1 == '.' )
	        return( 1 );

	    if( c2 == '.' )
	        return( -1 );
	    }

	    return( c1 - c2 );
        }

	return (*e1)->Slot() - (*e2)->Slot();	
}

/*
 * There RHS of a stream type map may have 'type value'
 * cruft on the start of teh map entry that we must skip..
 */
static int
sortcmpstreamsrhs( const void *a1, const void *a2 )
{
        int c1, c2;
	MapItem **e1 = (MapItem **)a1;
	MapItem **e2 = (MapItem **)a2;
	char *str1 = (*e1)->Rhs()->Text();
	char *str2 = (*e2)->Rhs()->Text();
	
	int i = 0;
	int j = 0;

	// skip type values on the start of the RHS
	if( ( c1 = str1[ 0 ] ) == '%' || isdigit( c1 ) )
	{
	    while( ( c1 = str1[ i ] ) != '/' )
	        i++;
	}
	if( ( c2 = str2[ 0 ] ) == '%' || isdigit( c2 ) )
	{
	    while( ( c2 = str2[ j ] ) != '/' )
	        j++;
	}

	for(; ( c1 = str1[ i ] ) && ( c2 = str2[ j ] ); i++, j++ )
	{
  
	    if( c1 == c2 )
	        continue;

	    if( 0 == strcmp( &str1[ i ], "...") )
	        return( -1 );

	    if( 0 == strcmp( &str2[ j ], "...") )
	        return( 1 );

	    if( c1 == '*' )
	        return( -1 );

	    if( c2 == '*' )
	        return( 1 );

	    if( c1 == '/' )
	        return( -1 );

	    if( c2 == '/' )
	        return( 1 );

	    // starting with 2013.1, this becomes non-default behavior.

	    if( p4tunable.Get( P4TUNE_STREAMVIEW_DOTS_LOW ) )
	    {
	    // make '.' lower than anything else
	    if( c1 == '.' )
	        return( 1 );

	    if( c2 == '.' )
	        return( -1 );
	    }

	    return( c1 - c2 );
        }

	return (*e1)->Slot() - (*e2)->Slot();	
}

} //extern "C"

MapItem **
MapTable::Sort( MapTableT direction, int streamFlag )
{
	// Both Strings and MakeTree want this.

	/*
	 * We cache only non-stream sort results.
	 * Stream sort calls happen at most once per MapTable instance
	 * (in the td tests, so probably also in real life).
	 * Incidentally, td measured an average of 1.45 non-stream sort calls
	 * per instance, so not a huge win there either.
	 * No instances received both stream and non-stream sort calls,
	 * but we check just in case the usage changes in the future.
	 */
	if( !streamFlag && trees[ direction ].sort )
	    return trees[ direction ].sort;

	// Create sort tree

	MapItem **vec = new MapItem *[count];
	MapItem **vecp;

	MapItem *map;

	for( vecp = vec, map = entry; map; map = map->Next() )
	    *vecp++ = map;

	// MACHTEN (gcc 2.3.3) belched at dir==LHS?lhs:rhs
	// Thus this 'if'.
	if( streamFlag )
	{
	    if( direction == LHS )
	        qsort( (char *)vec, count, sizeof( *vec ), sortcmpstreamslhs );
	    else
	        qsort( (char *)vec, count, sizeof( *vec ), sortcmpstreamsrhs );
	    return vec;
	}
	else
	{
	    if( direction == LHS )
	        qsort( (char *)vec, count, sizeof( *vec ), sortcmplhs );
	    else
	        qsort( (char *)vec, count, sizeof( *vec ), sortcmprhs );

	    // save it
	    return trees[ direction ].sort = vec;
	}
}

//
// Map tree construction
//

void
MapTable::MakeTree( MapTableT dir )
{
	int depth = 0;

	MapItem **vec = Sort( dir );

	trees[ dir ].tree = MapItem::Tree( vec, vec + Count(), dir, 0, depth );
	trees[ dir ].depth = depth;
}

//
// MapTable::Better - which table is better for matching?
// 

int
MapTable::Better( MapTable &other, MapTableT dir )
{
	// If we couldn't make a better map because of
	// wildcard explosion, this isn't better than the other.

	if( emptyReason == &MsgDb::TooWild )
	    return 0;

	// Compute the search trees, so we can compare depth.

	if( !trees[ dir ].tree )
	    MakeTree( dir );

	if( !other.trees[ dir ].tree )
	    other.MakeTree( dir );

	// shallower depth generally means faster matching

	return trees[ dir ].depth < other.trees[ dir ].depth;
}

//
// MapStrings construction
//

MapStrings *
MapTable::Strings( MapTableT direction )
{
	MapItem **vec = Sort( direction );
	MapStrings *strings = new MapStrings();
	MapHalf *oMapHalf = 0;
	int oHasSubDirs = 0;

	for( int i = 0; i < count; i++ )
	{
	    // If this is an unmapping, we're not going to get any
	    // satisfaction looking for strings.  Just skip it.

	    if( vec[i]->Flag() == MfUnmap )
		continue;

	    // Find out how much of MapHalf is fixed (non wildcard)
	    // and how much of that matches the saved MapHalf.
	    // Note that match <= fixedLen, because we only match
	    // the fixed portion.

	    MapHalf *mapHalf = vec[i]->Ths( direction );

	    if( oMapHalf )
	    {
		int match = oMapHalf->GetCommonLen( mapHalf );

		if( DEBUG_STRINGS )
		    p4debug.printf( "MapStrings: %s match %d fixed %d\n",
			    mapHalf->Text(), match, 
			    mapHalf->GetFixedLen() );

		// If this MapHalf matched the whole fixed part of the 
		// saved MapHalf (GetCommonLen() can match no more), 
		// then this MapHalf's is a substring of the saved,
		// and so won't needs its own string.

		// But: if this MapHalf has subdirectories, we'll have
		// to mark the saved MapHalf's string as having them.

		if( match == oMapHalf->GetFixedLen() )
		{
		    oHasSubDirs |= mapHalf->HasSubDirs( match );
		    continue;
		}

		// Output old string if new is not substring.
		// Then continue with valid part of new

		if( mapHalf->GetFixedLen() > match )
		    strings->Add( oMapHalf, oHasSubDirs );
	    }

	    oMapHalf = mapHalf;
	    oHasSubDirs = mapHalf->HasSubDirs( mapHalf->GetFixedLen() );
	}

	// We've held onto oMapHalf for the possibility that a new
	// mapHalf would be an initial substring.  Now that there are
	// no more mapHalfs, output the oMapHalf.

	if( oMapHalf )
	    strings->Add( oMapHalf, oHasSubDirs );

	if( DEBUG_STRINGS )
	    strings->Dump();

	return strings;
}

//
// MapTable::Check() - see if lhs matches map
//

MapItem *
MapTable::Check(
	MapTableT dir,
	const StrPtr &from )
{
	if( !trees[ dir ].tree )
	    MakeTree( dir );

	return trees[ dir ].tree->Match( dir, from );
}

//
// MapTable::Translate() - map an lhs into an rhs
//

MapItem *
MapTable::Translate(
	MapTableT dir,
	const StrPtr &from,
	StrBuf &to )
{
        Error e;
	if( !trees[ dir ].tree )
	    MakeTree( dir );

	MapItem *map = trees[ dir ].tree->Match( dir, from );

	// Expand into target string.
	// We have to Match2 here, because the last Match2 done in
	// MapItem::Match may not have been the last to succeed.

	if( map )
	{
	    MapParams params;

	    map->Ths( dir )->Match2( from, params );
	    map->Ohs( dir )->Expand( from, to, params );

	    if( DEBUG_TRANS )
		p4debug.printf( "MapTrans: %s (%d) -> %s\n", 
		    from.Text(), map->Slot(), to.Text() );
	}

	return map;
}
//
// MapTable::Match() - just match pattern against string
//

int
MapTable::Match(
	MapHalf *l,
	const StrPtr &rhs )
{
	MapParams params;
	return l->Match( rhs, params );
}

//
// MapTable::Match() - just match pattern against string
//

int
MapTable::Match(
	const StrPtr &lhs,
	const StrPtr &rhs )
{
	MapHalf l;
	l = lhs;
	MapParams params;
	return l.Match( rhs, params );
}

//
// MapTable::ValidDepotMap() - return 1 if map is a valid depot map entry
//

int
MapTable::ValidDepotMap( const StrPtr &map )
{
	MapHalf l;
	l = map;

	// Valid depot map has only one wildcard, and it must
	// be a trailing wildcard of the form '/...'

	return l.WildcardCount() == 1 && l.HasEndSlashEllipses();
}

//
// MapTable::Get() - get a MapTable entry
//

MapItem *
MapTable::Get( int n )
{
	MapItem *map;

	for( map = entry; map; map = map->Next() )
	    if( !n-- )
		return map;

	return 0;
}

//
// MapItem accessors
//

int
MapTable::GetSlot( MapItem *m )
{
	return count - m->Slot() - 1;
}

MapFlag
MapTable::GetFlag( MapItem *m )
{
	return m->Flag();
}

MapItem *
MapTable::GetNext( MapItem *m )
{
	return m->Next();
}

const StrPtr *
MapTable::GetStr( MapItem *m, MapTableT dir )
{
	return m->Ths( dir );
}

int
MapTable::Translate( 
	MapItem *m,
	MapTableT dir,
	const StrPtr &from,
	StrBuf &to )
{
	MapParams params;

	if( m->Flag() == MfUnmap )
	    return 0;

	if( !m->Ths( dir )->Match( from, params ) )
	    return 0;

	// Expand into target string.

	m->Ohs( dir )->Expand( from, to, params );

	return 1;
}

/*
 * MapTable::StripMap() - return copy without mapFlag entries.
 */

MapTable *
MapTable::StripMap( MapFlag mapFlag )
{
	MapTable *m0 = new MapTable;
	MapItem *map;

	for( map = entry; map; map = map->Next() )
	    if( map->Flag() != mapFlag )
		m0->Insert( *map->Lhs(), *map->Rhs(), map->Flag() );

	m0->Reverse();

	return m0;
}

/*
 * MapTable::Swap() - return copy with LHS and RHS swapped for each MapItem.
 */

MapTable *
MapTable::Swap( MapTable *table )
{
	MapTable *m0 = new MapTable;
	MapItem *map;

	for( map = entry; map; map = map->Next() )
	    m0->Insert( *map->Rhs(), *map->Lhs(), map->Flag() );

	m0->Reverse();

	return m0;

}

int
MapTable::CountByFlag( MapFlag mapFlag )
{
	int result = 0;
	MapItem *map;

	for( map = entry; map; map = map->Next() )
	    result += ( map->Flag() == mapFlag );

	return result;
}

void
MapTable::InsertByPattern( 
	const StrPtr &lhs, 
	const StrPtr &rhs, 
	MapFlag mapFlag )
{
	char *l = lhs.End();
	char *r = rhs.End();
	char *ls = lhs.Text();
	char *rs = rhs.Text();
	int slashes;

	// Insist on starting after //xxx/

	for( slashes = 0; slashes < 3 && ls < l; ++ls )
	    slashes += *ls == '/';

	for( slashes = 0; slashes < 3 && rs < r; ++rs )
	    slashes += *rs == '/';

	// Find matching ending substring

	slashes = 0;

	while( l > ls && r > rs && StrPtr::SEqual( l[-1], r[-1] ) )
	{
	    --l, --r;
	    slashes += *l == '/';
	}

	// Don't strip off the last mismatching /

	if( l < lhs.End() && *l == '/' )
	    ++l, ++r, --slashes;

	// Don't strip off trailing . if we are adding ...

	if( ( ( l < lhs.End() && l[-1] == '.' ) ||
	      ( r < rhs.End() && r[-1] == '.' ) ) && slashes )
	    ++l, ++r;

	// Replace end with * or ...
	// And put it on the map

	if( slashes && l < lhs.End() - 3 )
	{
	    StrBuf left;
	    left.Append( lhs.Text(), l - lhs.Text() );
	    left.Append( "...", 3 );

	    StrBuf right;
	    right.Append( rhs.Text(), r - rhs.Text() );
	    right.Append( "...", 3 );

	    InsertNoDups( left, right, mapFlag );
	}
	else if( !slashes && l < lhs.End() - 1 )
	{
	    StrBuf left;
	    left.Append( lhs.Text(), l - lhs.Text() );
	    left.Append( "*", 1 );

	    StrBuf right;
	    right.Append( rhs.Text(), r - rhs.Text() );
	    right.Append( "*", 1 );

	    InsertNoDups( left, right, mapFlag );
	}
	else
	    InsertNoDups( lhs, rhs, mapFlag );
}